📌 ¿Qué es la Complejidad Algorítmica?

La complejidad algorítmica es el estudio de cómo el rendimiento de un algoritmo cambia en función del tamaño de la entrada. Nos ayuda a entender cuán eficiente es un algoritmo en términos de tiempo y espacio.

Por ejemplo, si tenemos dos formas de resolver un problema, queremos elegir la que sea más rápida y use menos memoria.

✅ Ejemplo de un problema simple:

Queremos sumar los primeros n números naturales.

Diferentes formas de resolverlo:

Usando un bucle (sumamos uno por uno).
Usando una fórmula matemática (más eficiente).

Veamos ambos enfoques en varios lenguajes.

Ejemplo 1: Suma con un bucle (O(n))

1public class SumNumbers {
2    public static int sum(int n) {
3        int total = 0;
4        for (int i = 1; i <= n; i++) {
5            total += i;
6        }
7        return total;
8    }
9
10    public static void main(String[] args) {
11        System.out.println(sum(100)); // 5050
12    }
13}

Ejemplo 2: Suma con fórmula matemática (O(1))

1public class SumFormula {
2    public static int sum(int n) {
3        return n * (n + 1) / 2;
4    }
5
6    public static void main(String[] args) {
7        System.out.println(sum(100)); // 5050
8    }
9}

📌 Diferencia entre Complejidad Temporal y Espacial

⏳ Complejidad Temporal

Se refiere a cuánto tiempo tarda un algoritmo en ejecutarse en función de la cantidad de datos.
Se mide en función del tamaño de la entrada n.

💾 Complejidad Espacial

Se refiere a cuánta memoria utiliza un algoritmo.
Un algoritmo que almacena todos los datos en un array consume más memoria que uno que usa solo unas pocas variables.

✅ Ejemplo de espacio usado en memoria

1public class ArrayExample {
2    public static int[] createArray(int n) {
3        int[] arr = new int[n];
4        for (int i = 0; i < n; i++) {
5            arr[i] = i;
6        }
7        return arr;
8    }
9}

Este algoritmo usa O(n) de memoria porque almacena todos los números en un array.
Si solo queremos sumarlos sin almacenarlos, usamos O(1), como en la función de suma sin array.