Introducción a la Eficiencia Algorítmica (Big O)

Entender la notación Big O es la diferencia entre un código que funciona bien en tu local con 10 datos y uno que tumba el servidor cuando llegan 100,000 usuarios. No se trata de medir segundos exactos (que dependen del hardware), sino de medir cómo crece el número de operaciones conforme crecen los datos de entrada ( $N$ ).

Visualizando la Complejidad

Para entender el impacto, observemos cómo se comportan las distintas complejidades cuando $N$ aumenta.

$O(1)$ (Verde): Tiempo constante. No importa si $N$ es 1 o 1 millón, tarda lo mismo.
$O(N)$ (Azul): Crecimiento lineal. Si duplicas los datos, duplicas el tiempo.
$O(N^2)$ (Rojo): Crecimiento cuadrático. El rendimiento se degrada exponencialmente. ¡Peligro!

Walkthrough: La suma de 1 a N

Vamos a comparar dos formas de resolver el mismo problema: Sumar todos los números desde 1 hasta $N$ .

Enfoque A: El Bucle (Iterativo)

La forma intuitiva es recorrer los números uno a uno y acumularlos.

function sumaIterativa(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

Análisis: Si $N = 10$ , el bucle corre 10 veces. Si $N = 1,000$ , corre 1,000 veces. El número de operaciones crece directamente con la entrada. Complejidad: $O(N)$ .

Enfoque B: La Fórmula (Matemático)

Usando la fórmula de la suma de Gauss:

Sum = \frac{n(n+1)}{2}

El código se ve así:

function sumaMatematica(n) {
  return (n * (n + 1)) / 2;
}

Análisis: Aquí realizamos: 1 multiplicación, 1 suma y 1 división. Total: 3 operaciones. Si $N = 10$ , son 3 operaciones. Si $N = 1,000,000$ , siguen siendo 3 operaciones. Complejidad: $O(1)$ .

Análisis Guiado: Bucles Dependientes

A menudo pensamos que dos bucles anidados siempre son simplemente $N \times N$ , pero ¿qué pasa cuando el bucle interno depende del externo?

Mira este código:

for (let i = 0; i < n; i++) {
  for (let j = 0; j < i; j++) {
    console.log(i, j);
  }
}

Pista: Esto es una suma de serie aritmética.

Cuando $i=0$ , el bucle interno corre 0 veces.
Cuando $i=1$ , corre 1 vez.
Cuando $i=N$ , corre $N$ veces.

Matemáticamente, el total de ejecuciones es:

\sum_{i=0}^{N-1} i = \frac{(N-1)N}{2} = \frac{N^2 - N}{2}

En Big O, ignoramos las constantes ( $/2$ ) y los términos no dominantes ( $-N$ ). Nos quedamos con el término que crece más rápido. Resultado: $O(N^2)$ .

Tarea Práctica: El costo de la fuerza bruta

Imagina que tienes una lista de IDs de usuarios y quieres encontrar si hay duplicados. Una solución de “fuerza bruta” compara cada elemento con todos los demás.

function tieneDuplicados(lista) {
  for (let i = 0; i < lista.length; i++) {
    for (let j = 0; j < lista.length; j++) {
      // Si son índices distintos pero mismo valor
      if (i !== j && lista[i] === lista[j]) {
        return true;
      }
    }
  }
  return false;
}

El Reto

Calcula teóricamente el impacto de este código si tu lista tiene 1,000,000 de usuarios ( $N = 10^6$ ).

Complejidad: $O(N^2)$ .
Operaciones: $(10^6)^2 = 10^{12}$ (Un billón de comparaciones).

Perspectiva de tiempo: Si tu procesador puede hacer 100 millones de operaciones por segundo ( $10^8$ ), ¿cuánto tardará este script?

\text{Tiempo} = \frac{10^{12} \text{ ops}}{10^8 \text{ ops/sec}} = 10,000 \text{ segundos}

Eso son aproximadamente 2.7 horas para una tarea que, con un algoritmo mejor optimizado (como un mapa hash $O(N)$ ), tardaría milisegundos.

Explorar

Blog

Roadmaps