Complejidad Algorítmica

¿Qué es la complejidad algorítmica?

La complejidad algorítmica nos permite medir qué tan eficiente es un algoritmo en términos de tiempo y espacio. Es fundamental para escribir código que funcione dentro de los límites de tiempo de las competencias.

Notación Big O

La notación Big O describe el comportamiento asintótico de un algoritmo, es decir, cómo crece el tiempo de ejecución cuando el tamaño de entrada aumenta.

Complejidades comunes

Ejemplos prácticos

O(1) - Tiempo constante

int obtenerPrimero(vector<int>& arr) {
    return arr[0];  // Siempre una operación
}

O(n) - Tiempo lineal

int suma(vector<int>& arr) {
    int total = 0;
    for (int x : arr) {     // n operaciones
        total += x;
    }
    return total;
}

O(n²) - Tiempo cuadrático

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {         // n veces
        for (int j = 0; j < n - 1; j++) { // n veces
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

O(log n) - Tiempo logarítmico

int busquedaBinaria(vector<int>& arr, int objetivo) {
    int izq = 0, der = arr.size() - 1;
    while (izq <= der) {
        int mid = izq + (der - izq) / 2;
        if (arr[mid] == objetivo) return mid;
        if (arr[mid] < objetivo) izq = mid + 1;
        else der = mid - 1;
    }
    return -1;
}

Reglas para calcular complejidad

1. Operaciones consecutivas se suman

void ejemplo(int n) {
    // O(n)
    for (int i = 0; i < n; i++) { }

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

2. Loops anidados se multiplican

void ejemplo(int n) {
    for (int i = 0; i < n; i++) {        // O(n)
        for (int j = 0; j < n; j++) {    // O(n)
            // operación O(1)
        }
    }
}
// Total: O(n) × O(n) = O(n²)

3. Se ignoran constantes

• O(2n) → O(n)
• O(n + 100) → O(n)
• O(3n² + 5n) → O(n²)

4. Se toma el término dominante

• O(n² + n) → O(n²)
• O(n³ + n² + n) → O(n³)

Tabla de referencia rápida

Esta tabla te ayuda a elegir la complejidad adecuada según el tamaño de entrada:

Complejidad de espacio

Además del tiempo, también debemos considerar la memoria:

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

// O(n) espacio - crea una copia
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;
}

Ejercicio práctico

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

void misterio(int n) {
    for (int i = 1; i <= n; i *= 2) {
        for (int j = 0; j < n; j++) {
            cout << i << " " << j << endl;
        }
    }
}

Ver respuesta

Respuesta: O(n log n)

• El loop externo ejecuta log₂(n) veces (i se duplica cada iteración)
• El loop interno ejecuta n veces
• Total: O(n log n)

Siguiente paso

Ahora que entiendes la complejidad, aprende sobre búsqueda binaria, uno de los algoritmos más importantes.