Complejidad Algorítmica

¿Por qué importa la velocidad de un programa?

Imagina que tienes una lista de 1,000,000 de números y necesitas encontrar uno específico. Tienes dos opciones:

• Opción A: Revisar uno por uno desde el principio hasta encontrarlo. En el peor caso, revisarías los 1,000,000 de números.
• Opción B: Si la lista está ordenada, puedes usar una técnica inteligente: abres la lista por la mitad, ves si el número que buscas es mayor o menor, y descartas la mitad que no te sirve. Repites esto hasta encontrarlo. Solo necesitarías unas 20 comparaciones.

¿La diferencia? La opción A hace 1,000,000 de operaciones. La opción B hace 20. Es una diferencia brutal. La complejidad algorítmica es la herramienta que nos permite medir y comparar estas diferencias.

En competencias de programación, tu programa tiene un tiempo límite (generalmente 1 o 2 segundos). Si tu solución es muy lenta, el juez te marcará "Tiempo Límite Excedido" (TLE), aunque tu respuesta sea correcta. Por eso, no basta con que tu programa funcione; debe funcionar rápido.

¿Qué es la notación Big O?

La notación Big O (se lee "O grande" o "orden de") es una forma matemática de describir cómo crece el tiempo de ejecución de un algoritmo cuando el tamaño de la entrada aumenta.

Vamos a desglosar esto:

• O es simplemente el símbolo que usamos. Puedes pensar en él como "Orden de magnitud".
• n representa el tamaño de la entrada. Si te dan un arreglo de 100 números, n = 100. Si te dan 1,000,000, n = 1,000,000.
• Lo que va dentro de los paréntesis describe la relación entre n y el número de operaciones.

Por ejemplo:

• O(n) significa que si n se duplica, el tiempo se duplica. La relación es proporcional.
• O(n²) significa que si n se duplica, el tiempo se cuadruplica ($2^2 = 4$). Crece mucho más rápido.

Analogía: el cartero

Imagina un cartero que entrega cartas en un vecindario:

• O(1): El cartero siempre entrega una carta en la casa de enfrente. No importa cuántas casas haya en el vecindario, siempre tarda lo mismo.
• O(n): El cartero tiene que entregar una carta a cada casa. Si hay 100 casas, visita 100. Si hay 1,000, visita 1,000.
• O(n²): El cartero tiene que entregar una carta a cada casa, pero después de cada entrega vuelve a la oficina (que está al inicio de la calle) a buscar la siguiente. Va y viene muchas veces.
• O(log n): El cartero tiene un directorio ordenado y busca la dirección como en un diccionario: abre por la mitad, descarta la mitad que no le sirve, y repite.

Complejidades comunes explicadas

O(1) — Tiempo constante

El algoritmo siempre tarda lo mismo, sin importar el tamaño de la entrada. Como prender un interruptor de luz: no importa si tu casa tiene 2 cuartos o 20, prender un interruptor toma el mismo tiempo.

// Ejemplo: acceder a un elemento de un arreglo por su posición
int obtenerPrimero(vector<int>& arr) {
    return arr[0];  // Siempre es UNA sola operación
}

¿Por qué es O(1)? No importa si el arreglo tiene 10 o 10 millones de elementos, acceder a arr[0] siempre toma la misma cantidad de tiempo. La computadora sabe exactamente dónde está ese dato en la memoria.

Ejemplos en la vida real: Buscar un contacto en tu teléfono por su nombre (si ya lo tienes guardado), sacar el primer plato de una pila.

---

O(log n) — Tiempo logarítmico

El algoritmo reduce el problema a la mitad en cada paso. Es increíblemente eficiente. Piensa en cómo buscas una palabra en un diccionario físico: no lees página por página desde el inicio. Abres el diccionario por la mitad, ves si la palabra que buscas está antes o después, y repites con la mitad correspondiente.

// Ejemplo: búsqueda binaria
int busquedaBinaria(vector<int>& arr, int objetivo) {
    int izq = 0, der = arr.size() - 1;

    while (izq <= der) {
        int mid = izq + (der - izq) / 2;  // Encontrar el punto medio

        if (arr[mid] == objetivo) return mid;       // ¡Lo encontramos!
        if (arr[mid] < objetivo) izq = mid + 1;     // Buscar en la mitad derecha
        else der = mid - 1;                          // Buscar en la mitad izquierda
    }

    return -1;  // No se encontró
}

¿Por qué es O(log n)? En cada iteración del while, descartamos la mitad de los elementos. Si tenemos 1,000,000 de elementos:

• Paso 1: quedan 500,000
• Paso 2: quedan 250,000
• Paso 3: quedan 125,000
• ... después de ~20 pasos: queda 1 elemento

$\log_2(1,000,000) \approx 20$. ¡Solo 20 pasos para buscar entre un millón!

Ejemplos en la vida real: Buscar una palabra en un diccionario, adivinar un número del 1 al 100 usando "mayor o menor", encontrar un nombre en un directorio telefónico.

---

O(n) — Tiempo lineal

El algoritmo visita cada elemento una vez. Si la entrada se duplica, el tiempo se duplica. Como contar cuántas personas hay en una fila: necesitas ver a cada persona una por una.

// Ejemplo: sumar todos los elementos de un arreglo
int suma(vector<int>& arr) {
    int total = 0;           // Empezamos con total = 0
    for (int x : arr) {      // Para CADA elemento x del arreglo...
        total += x;           // ...sumamos x al total
    }
    return total;             // Regresamos la suma
}

¿Por qué es O(n)? El ciclo for recorre cada elemento exactamente una vez. Si el arreglo tiene 100 elementos, el ciclo se ejecuta 100 veces. Si tiene 1,000,000, se ejecuta 1,000,000 de veces. La relación es directamente proporcional.

Ejemplos en la vida real: Contar cuántos alumnos hay en un salón (necesitas ver a cada uno), leer un libro completo, buscar algo en una lista no ordenada.

---

O(n log n) — Tiempo log-lineal

Esta complejidad aparece en los algoritmos de ordenamiento eficientes. Es como si por cada elemento (n), hicieras una búsqueda binaria (log n). Es la complejidad del sort() de C++.

// Ejemplo: ordenar un arreglo
vector<int> arr = {5, 2, 8, 1, 9, 3};
sort(arr.begin(), arr.end());
// Ahora arr = {1, 2, 3, 5, 8, 9}

Ejemplos en la vida real: Ordenar una baraja de cartas usando merge sort, organizar una lista de nombres alfabéticamente de forma eficiente.

---

O(n²) — Tiempo cuadrático

El algoritmo tiene dos ciclos anidados, cada uno recorriendo n elementos. Si n se duplica, el tiempo se cuadruplica. Como si cada persona en un salón tuviera que saludar de mano a todas las demás personas.

// Ejemplo: Bubble Sort (ordenamiento burbuja)
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {            // Recorremos n veces
        for (int j = 0; j < n - 1; j++) {    // Por cada vez, comparamos n-1 pares
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);    // Intercambiamos si están desordenados
            }
        }
    }
}

¿Por qué es O(n²)? Tenemos un ciclo dentro de otro. El ciclo externo se ejecuta n veces, y por cada una de esas veces, el ciclo interno se ejecuta ~n veces. Total: n × n = n².

Si n = 1,000, hacemos 1,000,000 de operaciones. Si n = 10,000, hacemos 100,000,000. ¡Crece muy rápido!

Ejemplos en la vida real: En una fiesta de 100 personas, si cada persona saluda a todas las demás, hay 100 × 99 / 2 ≈ 5,000 saludos. Si son 1,000 personas, ¡hay casi 500,000 saludos!

---

O(2ⁿ) — Tiempo exponencial

El tiempo se duplica con cada elemento adicional. Es extremadamente lento para entradas grandes. Como si tuvieras que probar todas las combinaciones posibles de una contraseña.

// Ejemplo: generar todos los subconjuntos
void subconjuntos(vector<int>& arr, int i, vector<int>& actual) {
    if (i == arr.size()) {
        // Imprimir actual
        return;
    }
    // Opción 1: incluir arr[i]
    actual.push_back(arr[i]);
    subconjuntos(arr, i + 1, actual);
    actual.pop_back();
    // Opción 2: no incluir arr[i]
    subconjuntos(arr, i + 1, actual);
}

¿Por qué es O(2ⁿ)? Para cada elemento, tenemos 2 opciones (incluirlo o no). Con n elementos: 2 × 2 × 2 × ... × 2 = 2ⁿ opciones.

Si n = 20, son ~1,000,000 de subconjuntos. Si n = 30, son ~1,000,000,000. ¡Con solo agregar 10 elementos, el tiempo se multiplica por 1,000!

---

O(n!) — Tiempo factorial

El tiempo crece como el factorial. Es la complejidad más lenta de las comunes. Aparece cuando generas todas las permutaciones (todos los posibles órdenes) de n elementos.

Con solo n = 12, ya son 479,001,600 permutaciones. Con n = 20, son más que todos los granos de arena del planeta.

Reglas para calcular la complejidad

Regla 1: Operaciones consecutivas se SUMAN

Si haces dos cosas una después de la otra, sumas sus complejidades:

void ejemplo(int n) {
    // Bloque 1: O(n)
    for (int i = 0; i < n; i++) {
        cout << i << " ";
    }

    // Bloque 2: O(n)
    for (int i = 0; i < n; i++) {
        cout << i * 2 << " ";
    }
}
// Total: O(n) + O(n) = O(2n) = O(n)

¿Por qué O(2n) se convierte en O(n)? Porque en Big O, las constantes no importan. Lo que nos interesa es cómo crece el tiempo, no el valor exacto. Tanto O(n) como O(2n) crecen de forma lineal.

Regla 2: Loops anidados se MULTIPLICAN

Si haces un ciclo dentro de otro, multiplicas sus complejidades:

void ejemplo(int n) {
    for (int i = 0; i < n; i++) {           // Este loop se ejecuta n veces
        for (int j = 0; j < n; j++) {       // Por cada i, este loop se ejecuta n veces
            cout << i << "," << j << " ";   // Esto se ejecuta n × n = n² veces
        }
    }
}
// Total: O(n) × O(n) = O(n²)

Regla 3: Se ignoran las constantes

• O(2n) → O(n) (la constante 2 no importa)
• O(n + 100) → O(n) (el 100 es insignificante cuando n es grande)
• O(3n² + 5n) → O(n²) (solo nos importa el término más grande)
• O(n/2) → O(n) (dividir por 2 es una constante)

¿Por qué ignoramos las constantes? Porque Big O mide el comportamiento a largo plazo. Si n = 1,000,000, la diferencia entre 2n y n es solo un factor de 2. Pero la diferencia entre n y n² es un factor de 1,000,000. Las constantes son "ruido" comparadas con los cambios fundamentales en cómo crece el tiempo.

Regla 4: Se toma el término dominante

Cuando hay varios términos, solo importa el que crece más rápido:

• O(n² + n) → O(n²) — cuando n es grande, n² domina sobre n
• O(n³ + n² + n) → O(n³) — n³ es el término más grande
• O(n + log n) → O(n) — n crece más rápido que log n

Es como comparar la velocidad de un avión (n²) con la de un auto (n). A distancias largas, el avión siempre gana, sin importar los detalles menores.

Comparación visual

Para entender la diferencia entre complejidades, veamos cuántas operaciones haría cada una para distintos valores de n:

Observa cómo O(2ⁿ) explota rapidísimo. Con n = 100, el número de operaciones es mayor que el número de átomos en el universo. Por eso, los algoritmos exponenciales solo sirven para entradas muy pequeñas.

¿Cómo saber qué complejidad necesitas?

Usa esta tabla como referencia rápida. Si el problema te dice que n puede ser hasta cierto valor, necesitas un algoritmo con la complejidad indicada:

Complejidad de espacio (memoria)

Además del tiempo, también debemos considerar cuánta memoria usa nuestro programa. La memoria también tiene límites (generalmente 256 MB).

// O(1) espacio — solo usa unas pocas variables
int suma(vector<int>& arr) {
    int total = 0;
    for (int x : arr) total += x;
    return total;
}

// O(n) espacio — crea un arreglo nuevo del mismo tamaño
vector<int> duplicar(vector<int>& arr) {
    vector<int> resultado(arr.size());
    for (int i = 0; i < arr.size(); i++) {
        resultado[i] = arr[i] * 2;
    }
    return resultado;
}

Regla práctica: Un int ocupa 4 bytes. Un arreglo de 10⁶ enteros ocupa ~4 MB. Un arreglo de 10⁸ enteros ocupa ~400 MB (¡posiblemente demasiado!).

Ejercicio práctico

¿Cuál es la complejidad de este código?

void misterio(int n) {
    for (int i = 1; i <= n; i *= 2) {       // ¿Cuántas veces se ejecuta?
        for (int j = 0; j < n; j++) {        // Este loop se ejecuta n veces
            cout << i << " " << j << endl;
        }
    }
}

Piénsalo antes de ver la respuesta...

Ver respuesta

Respuesta: O(n log n)

Analicemos:

• Loop externo: i empieza en 1 y se multiplica por 2 en cada iteración (1, 2, 4, 8, 16, ...). ¿Cuántas veces se ejecuta? Se ejecuta hasta que i > n, lo cual ocurre después de $\log_2(n)$ pasos. Por ejemplo, si n = 16: i toma los valores 1, 2, 4, 8, 16 → 5 pasos = $\log_2(16) + 1$.
• Loop interno: Se ejecuta exactamente n veces por cada iteración del loop externo.
• Total: $\log_2(n) \times n = n \log n$ → O(n log n)

Resumen

Siguiente paso

Ahora que entiendes cómo medir la eficiencia, dirígete a Fundamentos para aprender sobre pensamiento lógico y el concepto formal de algoritmo.