La complejidad temporal mide cómo crece el tiempo de ejecución de un algoritmo a medida que aumenta el tamaño de la entrada (n).

📌 Ejemplo:
Si un algoritmo tarda 1 segundo en ejecutarse con n = 10, pero tarda 100 años con n = 50, entonces su tiempo de ejecución crece de forma explosiva.

✅ Objetivo:
Queremos elegir el algoritmo más eficiente para evitar explosiones combinatorias que hagan que nuestro código sea inviable para grandes valores de n.

📌 Comparación de Complejidades

https://praveendavidmathew.medium.com/big-o-notation-understanding-different-time-complexities-72fe847a6343

📌 Tipos de Complejidad Temporal

Aquí veremos las principales complejidades temporales, desde las más rápidas hasta las más lentas.

1. O(1) - Complejidad Constante

📌 Ejemplo: Acceder a un índice en un array
No importa si el array tiene 10 o 1 millón de elementos, el acceso es instantáneo.

1public class ConstantTime {
2    public static int getElement(int[] arr, int index) {
3        return arr[index];
4    }
5}

2. O(log n) - Complejidad Logarítmica

📌 Ejemplo: Búsqueda Binaria
Cada vez que buscamos un número en un array ordenado, reducimos el problema a la mitad en cada paso.

1// Java - O(log n) - Búsqueda binaria
2public class BinarySearch {
3    public static boolean search(int[] arr, int target) {
4        int left = 0, right = arr.length - 1;
5        while (left <= right) {
6            int mid = left + (right - left) / 2;
7            if (arr[mid] == target) return true;
8            if (arr[mid] < target) left = mid + 1;
9            else right = mid - 1;
10        }
11        return false;
12    }
13}

https://miro.medium.com/v2/resize:fit:1200/format:webp/1*4poxx4vMDQfGEq3HeswJoA.gif

3. O(n) - Complejidad Lineal

📌 Ejemplo: Recorrer un array
El tiempo de ejecución crece proporcionalmente con n.

1// Java - O(n) - Recorrer un array
2public class LinearTime {
3    public static void printArray(int[] arr) {
4        for (int num : arr) {
5            System.out.println(num);
6        }
7    }
8}

4. O(n²) - Complejidad Cuadrática

📌 Ejemplo: Comparar todos los pares de un array (bucle anidado) 📌 **Ejemplo: Si tienes n estudiantes y quieres comparar cada uno con todos los demás, el número de comparaciones será n * n.

1// Java - O(n²) - Comparar pares
2public class QuadraticTime {
3    public static void printPairs(int[] arr) {
4        for (int i = 0; i < arr.length; i++) {
5            for (int j = 0; j < arr.length; j++) {
6                System.out.println(arr[i] + ", " + arr[j]);
7            }
8        }
9    }
10}

5. O(2ⁿ) - Explosión Combinatoria (Ejemplo: Fibonacci Recursivo)

Cuando un algoritmo genera múltiples opciones en cada paso, el tiempo de ejecución se dispara exponencialmente.

📌 Ejemplo: Fibonacci recursivo sin optimización

• fib(10) hace 177 llamadas recursivas.
• fib(50) hace billones de llamadas.

1// Java - O(2ⁿ) - Fibonacci recursivo
2public class Fibonacci {
3    public static int fib(int n) {
4        if (n <= 1) return n;
5        return fib(n - 1) + fib(n - 2);
6    }
7}

🚀 Solución: Memorización o programación dinámica para evitar cálculos repetidos.

6. O(n!) - Factorial (Explosión Combinatoria Extrema)

El peor tipo de complejidad temporal. Se usa en problemas como el Problema del Viajero (Traveling Salesman Problem).

📌 Ejemplo: Generar todas las permutaciones posibles de n elementos

1// Java - O(n!) - Generar permutaciones
2import java.util.ArrayList;
3import java.util.List;
4
5public class FactorialTime {
6    public static void permute(List<Integer> nums, List<Integer> temp, boolean[] used) {
7        if (temp.size() == nums.size()) {
8            System.out.println(temp);
9            return;
10        }
11        for (int i = 0; i < nums.size(); i++) {
12            if (used[i]) continue;
13            used[i] = true;
14            temp.add(nums.get(i));
15            permute(nums, temp, used);
16            used[i] = false;
17            temp.remove(temp.size() - 1);
18        }
19    }
20
21    public static void main(String[] args) {
22        List<Integer> nums = List.of(1, 2, 3);
23        permute(nums, new ArrayList<>(), new boolean[nums.size()]);
24    }
25}

✅ Ejemplo real:
Si tienes n ciudades y quieres encontrar la ruta óptima para visitarlas todas, el número de posibles caminos es n!.

🛑 Explosión combinatoria extrema:

• Para n = 10 → 10! = 3,628,800 combinaciones.
• Para n = 20 → 2.4 trillones de combinaciones.

🚀 Solución: Algoritmos de aproximación (heurísticas y metaheurísticas) en lugar de fuerza bruta.