Optimización de código

✅ Objetivo:
Entender cómo diferentes algoritmos procesan los datos, cuánto tiempo tardan y cuánta memoria consumen.

📌 1. Búsqueda en un Array

Cuando queremos encontrar un elemento en un array, tenemos dos estrategias:

📌 Búsqueda Lineal (O(n))

Si el array no está ordenado, la única opción es revisar uno por uno hasta encontrar el elemento.

📌 Ejemplo: Búsqueda Lineal

1public class LinearSearch {
2    public static boolean search(int[] arr, int target) {
3        for (int num : arr) {
4            if (num == target) return true;
5        }
6        return false;
7    }
8}

✅ Análisis:

  • Complejidad temporal: O(n), ya que en el peor caso recorremos todo el array.
  • Complejidad espacial: O(1), ya que no usamos memoria extra.

📌 Búsqueda Binaria (O(log n))

Si el array está ordenado, podemos usar búsqueda binaria, que divide el problema a la mitad en cada paso.

📌 Ejemplo: Búsqueda Binaria

1public class BinarySearch {
2    public static int binarySearch(int[] arr, int target) {
3        int left = 0, right = arr.length - 1;
4        while (left <= right) {
5            int mid = left + (right - left) / 2;
6            if (arr[mid] == target) return mid;
7            if (arr[mid] < target) left = mid + 1;
8            else right = mid - 1;
9        }
10        return -1; // No encontrado
11    }
12
13    public static void main(String[] args) {
14        int[] numbers = {1, 3, 5, 7, 9, 11};
15        int target = 7;
16        int result = binarySearch(numbers, target);
17        System.out.println("Índice encontrado: " + result);
18    }
19}

✅ Análisis:

  • Complejidad temporal: O(log n), ya que descartamos la mitad en cada paso.
  • Complejidad espacial: O(1), no usamos memoria extra.

📌 Conclusión:

  • Si el array no está ordenado, usamos búsqueda lineal (O(n)).
  • Si el array está ordenado, usamos búsqueda binaria (O(log n), mucho más rápida).

📌 2. Algoritmos de Ordenación

Los algoritmos de ordenación organizan los datos de menor a mayor o de mayor a menor.

📌 Bubble Sort (O(n²))

Uno de los algoritmos más simples, pero ineficiente para listas grandes.

📌 Ejemplo: Bubble Sort

1import java.util.Arrays;
2
3public class BubbleSort {
4    public static void bubbleSort(int[] arr) {
5        int n = arr.length;
6        boolean swapped;
7        for (int i = 0; i < n - 1; i++) {
8            swapped = false;
9            for (int j = 0; j < n - i - 1; j++) {
10                if (arr[j] > arr[j + 1]) {
11                    int temp = arr[j];
12                    arr[j] = arr[j + 1];
13                    arr[j + 1] = temp;
14                    swapped = true;
15                }
16            }
17            if (!swapped) break; // Optimización: Si no hubo cambios, está ordenado
18        }
19    }
20
21    public static void main(String[] args) {
22        int[] numbers = {64, 34, 25, 12, 22, 11, 90};
23        bubbleSort(numbers);
24        System.out.println("Array ordenado: " + Arrays.toString(numbers));
25    }
26}

✅ Análisis:

  • Complejidad temporal: O(n²), ya que comparamos todos los pares posibles.
  • Complejidad espacial: O(1), ya que ordenamos en el mismo array.

📌 Conclusión:

  • No usar en listas grandes.
  • Más eficientes: QuickSort o MergeSort.

📌 Merge Sort (O(n log n))

Un algoritmo eficiente basado en Divide y Vencerás.

📌 Ejemplo: Merge Sort

1import java.util.Arrays;
2
3public class MergeSort {
4    public static void mergeSort(int[] arr, int left, int right) {
5        if (left < right) {
6            int mid = left + (right - left) / 2;
7            mergeSort(arr, left, mid);
8            mergeSort(arr, mid + 1, right);
9            merge(arr, left, mid, right);
10        }
11    }
12
13    private static void merge(int[] arr, int left, int mid, int right) {
14        int n1 = mid - left + 1;
15        int n2 = right - mid;
16
17        int[] leftArr = new int[n1];
18        int[] rightArr = new int[n2];
19
20        System.arraycopy(arr, left, leftArr, 0, n1);
21        System.arraycopy(arr, mid + 1, rightArr, 0, n2);
22
23        int i = 0, j = 0, k = left;
24        while (i < n1 && j < n2) {
25            if (leftArr[i] <= rightArr[j]) {
26                arr[k++] = leftArr[i++];
27            } else {
28                arr[k++] = rightArr[j++];
29            }
30        }
31
32        while (i < n1) arr[k++] = leftArr[i++];
33        while (j < n2) arr[k++] = rightArr[j++];
34    }
35
36    public static void main(String[] args) {
37        int[] numbers = {38, 27, 43, 3, 9, 82, 10};
38        mergeSort(numbers, 0, numbers.length - 1);
39        System.out.println("Array ordenado: " + Arrays.toString(numbers));
40    }
41}

✅ Análisis:

  • Complejidad temporal: O(n log n), ya que dividimos log n veces y combinamos O(n).
  • Complejidad espacial: O(n), ya que creamos nuevos arrays.

📌 Conclusión:

  • Merge Sort es más eficiente que Bubble Sort.
  • En la práctica, QuickSort es aún más rápido en la mayoría de los casos.

📌 QuickSort (O(n log n))

Un algoritmo eficiente basado en Divide y Vencerás.

📌 Ejemplo: Merge Sort

1import java.util.Arrays;
2
3public class QuickSort {
4    public static void quickSort(int[] arr, int low, int high) {
5        if (low < high) {
6            int pi = partition(arr, low, high);
7            quickSort(arr, low, pi - 1);
8            quickSort(arr, pi + 1, high);
9        }
10    }
11
12    private static int partition(int[] arr, int low, int high) {
13        int pivot = arr[high];
14        int i = low - 1;
15        for (int j = low; j < high; j++) {
16            if (arr[j] < pivot) {
17                i++;
18                int temp = arr[i];
19                arr[i] = arr[j];
20                arr[j] = temp;
21            }
22        }
23        int temp = arr[i + 1];
24        arr[i + 1] = arr[high];
25        arr[high] = temp;
26        return i + 1;
27    }
28
29    public static void main(String[] args) {
30        int[] numbers = {10, 7, 8, 9, 1, 5};
31        quickSort(numbers, 0, numbers.length - 1);
32        System.out.println("Array ordenado: " + Arrays.toString(numbers));
33    }
34}

✅ Análisis:

  • Complejidad temporal:

    • Peor caso (array ya ordenado y mal pivote): O(n²)
    • Mejor caso (pivote óptimo): O(n log n)
    • Caso promedio: O(n log n)

  • Complejidad espacial:

    • O(log n) en el mejor caso y caso promedio si se usa la versión in-place (que particiona el array sin usar listas auxiliares).
    • O(n) en el peor caso si se usa una versión con listas auxiliares.

📌 Conclusión:

  • En la práctica, QuickSort es aún más rápido en la mayoría de los casos.

📌 3. Algoritmos Recursivos y Complejidad

Los algoritmos recursivos llaman a sí mismos para resolver subproblemas más pequeños.

📌 Fibonacci Recursivo (O(2ⁿ))

📌 Ejemplo: Fibonacci sin optimización

1public class Fibonacci {
2    public static int fibonacci(int n) {
3        if (n <= 1) return n;
4        return fibonacci(n - 1) + fibonacci(n - 2);
5    }
6
7    public static void main(String[] args) {
8        int n = 10;
9        System.out.println("Fibonacci de " + n + ": " + fibonacci(n));
10    }
11}

✅ Análisis:

  • Complejidad temporal: O(2ⁿ), extremadamente lento.
  • Complejidad espacial: O(n), por la pila de recursión.

📌 Solución: Usar memorización (Programación Dinámica) para evitar cálculos repetidos.

1import java.util.HashMap;
2
3public class FibonacciMemo {
4    private static HashMap<Integer, Integer> memo = new HashMap<>();
5
6    public static int fibonacci(int n) {
7        if (n <= 1) return n;
8        if (memo.containsKey(n)) return memo.get(n);
9
10        int result = fibonacci(n - 1) + fibonacci(n - 2);
11        memo.put(n, result);
12        return result;
13    }
14
15    public static void main(String[] args) {
16        int n = 10;
17        System.out.println("Fibonacci de " + n + ": " + fibonacci(n));
18    }
19}

✅ Análisis:

  • Complejidad temporal: O(n), mejor que O(2ⁿ).
  • Complejidad espacial: O(n), por la memoria usada.

📌 Resumen de Complejidades

AlgoritmoMejor Caso (Ω)Peor Caso (O)Complejidad Espacial (S)
Búsqueda LinealO(1)O(n)O(1)
Búsqueda BinariaO(1)O(log n)O(1)
Bubble SortO(n)O(n²)O(1)
Merge SortO(n log n)O(n log n)O(n)
QuickSort (In-Place)O(n log n)O(n²)O(log n)
QuickSort (Arrays Auxiliares)O(n log n)O(n²)O(n)
Insertion SortO(n)O(n²)O(1)
Fibonacci RecursivoO(1)O(2ⁿ)O(n)
Fibonacci con MemorizaciónO(n)O(n)O(n)
    ← Complejidad EspacialVolver al cursoRecurrencias y el Método Maestro →