Complejidad

Crecimiento de complejidades

⚡ Tiempo Constante

Veamos nuestro primer ejemplo.

Este método recibe un array de enteros e imprime el primer elemento en consola.

👉 No importa si el array tiene 1 elemento o un millón: siempre se ejecuta una sola operación.

public class Main {
    public void log(int[] numbers) {
        // O(1)
        System.out.println(numbers[0]);
    }
}

⏱️ Complejidad del algoritmo

  • Aquí solo realizamos una operación.

  • Eso significa que este método se ejecuta en tiempo constante, denotado como:

\[ O(1) \]

⚡ Lo importante es que no depende del tamaño de la entrada. Incluso con millones de elementos, siempre accedemos al índice 0.

🔄 ¿Y si duplicamos la línea?

public class Main {
    public void log(int[] numbers) {
        // O(2)
        System.out.println(numbers[0]);
        System.out.println(numbers[0]);
    }
}

Ahora tenemos dos operaciones constantes. Matemáticamente sería:

\[ O(2) \]

Pero en notación Big-O simplificamos siempre a:

\[ O(1) \]

Porque lo que importa no es el número exacto de operaciones, sino cómo crece el tiempo de ejecución a medida que crece la entrada.

Este método siempre se ejecuta en tiempo constante sin importar el tamaño del array.

Esto es lo que llamamos complejidad O(1).

📏 Complejidad Lineal

En este caso tenemos un bucle que recorre todos los elementos de un array e imprime cada uno en consola.

Aquí sí importa el tamaño de la entrada.

public class Main {
    public void log(int[] numbers) {
        for (int i = 0; i < numbers.length; i++)
            System.out.println(numbers[i]);
    }
}

⏱️ Complejidad

Si el array tiene 1 elemento, hacemos 1 impresión.

Si tiene 1 millón de elementos, hacemos 1 millón de impresiones.

Por lo tanto, el coste del algoritmo crece linealmente con el tamaño de la entrada:

\[ O(n) \]

🔄 Variantes del bucle

Podemos usar:

  • for tradicional,
  • for-each,
  • while,
  • do-while.

El resultado será el mismo:

\[ O(n) \]

⚡ ¿Y si añadimos operaciones extra?

public class Main {
    public void log(int[] numbers) {
        System.out.println();      // O(1)
        for (int number: numbers)  // O(n)
            System.out.println(number);
        System.out.println();      // O(1)
    }
}

Este método tiene:

\[ O(1) + O(n) + O(1) = O(n+2) \]

Pero en notación Big-O omitimos las constantes:

\[ O(n+2) ;;\equiv;; O(n) \]

🔁 Dos bucles consecutivos

public class Main {
    public void log(int[] numbers) {
        for (int number: numbers)  // O(n)
            System.out.println(number);

        for (int number: numbers)  // O(n)
            System.out.println(number);
    }
}

Aquí tenemos:

\[ O(n) + O(n) = O(2n) \equiv O(n) \]

El crecimiento sigue siendo lineal.

🔀 Dos entradas diferentes

public class Main {
    public void log(int[] numbers, String[] names) {
        for (int number: numbers)   // O(n)
            System.out.println(number);

        for (String name: names)    // O(m)
            System.out.println(name);
    }
}

En este caso hay dos entradas distintas:

  • n = tamaño del array de números,
  • m = tamaño del array de nombres.

Por lo tanto:

\[ O(n) + O(m) \]

El tiempo de ejecución crece linealmente con el tamaño de la entrada (o entradas).

Por eso decimos que este algoritmo tiene complejidad \[O(n)\].

🌀 Bucles Anidados

Hasta ahora vimos que un bucle simple tiene complejidad: \[ O(n) \]

Pero, ¿qué pasa si tenemos un bucle dentro de otro?

public class Main {
    public void log(int[] numbers) {
        for (int first : numbers)     // O(n)
            for (int second : numbers) // O(n)
                System.out.println(first + ", " + second);
    }
}

⏱️ Complejidad

  • El primer bucle recorre los \(n\) elementos → \(O(n)\).
  • En cada iteración, el segundo bucle también recorre los \(n\) elementos → \(O(n)\).

Por lo tanto:

\[ O(n) \times O(n) = O(n^2) \]

Esto significa que el tiempo de ejecución crece cuadráticamente con el tamaño de la entrada.

🔄 Añadiendo un bucle externo

public class Main {
    public void log(int[] numbers) {
        for (int number : numbers)         // O(n)
            System.out.println(number);

        for (int first : numbers)          // O(n)
            for (int second : numbers)     // O(n)
                System.out.println(first + ", " + second);
    }
}

Aquí tenemos:

\[ O(n) + O(n^2) \]

Pero como \(n^2\) crece más rápido que \(n\), simplificamos:

\[ O(n + n^2) \equiv O(n^2) \]

🔼 Añadiendo aún más bucles

Si anidamos tres bucles:

public class Main {
    public void log(int[] numbers) {
        for (int first : numbers)
            for (int second : numbers)
                for (int third : numbers)
                    System.out.println(first + ", " + second + ", " + third);
    }
}

La complejidad ahora es:

\[ O(n) \times O(n) \times O(n) = O(n^3) \]

📈 Crecimiento

  • \(O(n)\) ➲ crece de forma lineal.

  • \(O(n^2)\) ➲ crece de forma cuadrática, mucho más rápido.

  • \(O(n^3)\) ➲ crece cúbicamente, aún más costoso.

Crecimiento de complejidades

Por ejemplo:

Tamaño de entrada (n) Operaciones O(n) Operaciones O(n^2) Operaciones O(n^3)
10 10 100 1,000
100 100 10,000 1,000,000
1000 1000 1,000,000 1,000,000,000

Cada bucle anidado multiplica el coste del algoritmo. Por eso:

  • Un bucle → \(O(n)\)
  • Dos bucles anidados → \(O(n^2)\)
  • Tres bucles anidados → \(O(n^3)\)

Y así sucesivamente 🚀

📉 Complejidad Logarítmica

Otra velocidad de crecimiento que debemos conocer es la logarítmica, representada como:

\[ O(\log n) \]

Mientras que la complejidad lineal (\(O(n)\)) crece en proporción directa al tamaño de la entrada,

la complejidad logarítmica crece rápidamente al inicio pero después se aplana, volviéndose mucho más lenta en su crecimiento.

Crecimiento de complejidades

🚀 Escalabilidad

Con búsqueda lineal (\(O(n)\)), si tenemos 1 millón de elementos, en el peor caso inspeccionamos los 1 millón.

Con búsqueda binaria (\(O(\log n)\)), en 1 millón de elementos necesitamos como máximo:

\[ \log_2(1{,}000{,}000) \approx 19 \]

¡Solo 19 pasos para encontrar la respuesta!

Los algoritmos logarítmicos son mucho más eficientes que los lineales y cuadráticos.

Cada paso reduce el problema a la mitad, haciendo que el crecimiento sea extremadamente lento y escalable.

💾 Complejidad Espacial

Ejemplo 1: espacio constante \(O(1)\)

En este método greet, solo declaramos una variable de bucle independiente del tamaño de la entrada.
Así que, aunque tengamos 10 o un millón de elementos, el espacio adicional será siempre el mismo:

public class Main {
    public void greet(String[] names) {
        // O(1) space
        for (int i = 0; i < names.length; i++) {
            System.out.println("Hi " + names[i]);
        }
    }
}

Idea clave: El espacio requerido no crece con el tamaño de la entrada, es constante.

Ejemplo 2: espacio lineal \(O(n)\)

Ahora supongamos que declaramos un nuevo array llamado copy, de la misma longitud que names.

public class Main {
    public void greet(String[] names) {
        // O(n) space
        String[] copy = new String[names.length];

        for (int i = 0; i < names.length; i++) {
            System.out.println("Hi " + names[i]);
        }
    }
}

Aquí la memoria adicional sí depende del tamaño de la entrada: si names tiene 1.000 elementos, copy también ocupará espacio para 1.000 elementos.

Por eso decimos que la complejidad espacial es \(O(n)\).

Nota importante

Cuando hablamos de complejidad espacial, no contamos el tamaño de la entrada (pues ya existe). Solo medimos el espacio extra que nuestro algoritmo necesita para ejecutarse.

⚡ En este curso nos enfocaremos en la complejidad temporal, ya que suele ser más crítica. Pero recuerda siempre reflexionar sobre la memoria, sobre todo cuando trabajes en dispositivos con recursos limitados.