El orden de un algoritmo es una medida teórica que nos ayuda a evaluar su eficiencia en términos de la cantidad de operaciones que realiza en función del tamaño de la entrada.
En el artículo anterior definimos qué es un algoritmo como una serie de pasos para resolver un problema. Pero claro, para un mismo problema existen cientos de soluciones posibles y no todos son igual de eficientes.
Por ejemplo, imagina que queremos buscar un nombre en un listado impreso un montón de hojas de papel, ordenado alfabéticamente.
- Opción A: Empiezas en la primera página, lees el primer nombre, luego el segundo… hasta encontrarlo.
- Opción B: Abres por la mitad. Si el nombre es anterior, te quedas con la primera mitad. Si es posterior, con la segunda. Repites el proceso dividiendo y descartando.
Ambos son algoritmos válidos. Ambos encontrarán el nombre. Pero si la guía tiene 1.000.000 de páginas, la Opción A tardará una eternidad, mientras que la Opción B lo encontrará muchísimo más rápido.
Aquí es donde entra la Complejidad algorítmica o notación O(..) (Big O). Una métrica de rendimiento que evalua cómo crece el tiempo de ejecución a medida que aumentan los datos.
La notación Big O no es exclusiva de programación, en realidad es un concepto heredado de las matemáticas, concretamente del análisis asintótico.
Sin embargo, hoy en día se conoce más por su uso en la programación, por la enorme difusión que tiene esta última (al fin y al cabo, hay más programadores que matemáticos).
¿Por qué no medimos en segundos?
¿Porqué complicarnos así? ¿Porqué no vale con “Mi algoritmo es rápido porque tarda 0.1 segundos”?
Primero, porque el tiempo es relativo al hardware. Ese mismo código puede tardar 0.1s en tu ordenador, pero tardar 2s en un móvil antiguo. Por tanto, los segundos no sólo miden la calidad del código, sino la potencia de la máquina.
Segundo, y más importante, porque nos interesa el crecimiento relativo. Un algoritmo puede ser muy rápido para 5 elementos (hacer 20 operaciones), pero dispararse a 10 millones de operaciones con solo 5000 elementos.
La Notación Big O(N)
Técnicamente, la notación Big O describe la Cota Superior Asintótica (Asymptotic Upper Bound), es decir, define el límite o techo de crecimiento de un algoritmo.
Básicamente nos dice:
En el peor de los casos, si meto N datos, el número de operaciones va a crecer de esta forma
Cómo generalmente (simplificando), el tiempo crece de forma similar a la cantidad de operaciones a realizar, también refleja el incremento de tiempo para pasar de una entrada N a otra.
N representa el tamaño de la entrada. Si ordenamos una lista de 10 números, N = 10. Si procesamos a todos los usuarios de Facebook, N = varios miles de millones.
Vamos a ver los tipos más comunes, ordenados de “mejor a peor” a “catastrófico”.
O(1) - Complejidad constante
Es el escenario ideal. Indica que el tiempo de ejecución es independiente del tamaño de la entrada. El algoritmo tarda exactamente lo mismo procesando 1 elemento que 1 millón.
Ejemplo: Acceder al primer elemento de un array. Saber qué hay en la posición 0 de una lista cuesta lo mismo si la lista es pequeña o gigante. Es una operación directa de memoria.
function obtenerPrimero(lista) {
return lista[0]; // Tiempo constante, independiente de lista.length
}
O(log n) - Complejidad logarítmica
Característica de los algoritmos de tipo divide y vencerás. Ocurre en algoritmos que, en cada paso, descartan la mitad de los datos
Su crecimiento es muy buen (es decir, bastante lento), lo que los hace muy escalables.
- Para N = 1.000 datos ≈ 10 operaciones
- Para N = 1.000.000 datos ≈ 20 operaciones 👍
Es la base de la Búsqueda Binaria o de las operaciones en árboles balanceados (como AVL o Red-Black Trees).
O(n) - Complejidad lineal
Es el caso “normal”. El tiempo de ejecución crece proporcionalmente a la entrada. Si duplicas los datos, el tiempo se duplica.
Esto sucede, por ejemplo, cuando necesitamos leer o procesar cada elemento al menos una vez.
Ejemplo: Un bucle for simple para encontrar el número mayor en una lista desordenada. Tienes que mirarlos todos obligatoriamente.
function buscarMaximo(lista) {
for (let i = 0; i < lista.length; i++) {
// Operaciones...
}
}
O(n · log n) - Complejidad Lineal-Logarítmica
Este es el estándar de eficiencia para algoritmos de ordenación. Matemáticamente, equivale a ejecutar una operación logarítmica n veces.
La mayoría de los algoritmos de ordenamiento eficientes (Merge Sort, Quick Sort, Heap Sort) caen en esta categoría. Es significativamente más rápido que n², pero más lento que n.
Si usas el método .sort() nativo de tu lenguaje (JavaScript, C#, Python), casi con total seguridad estás utilizando un algoritmo de complejidad O(n · log n).
O(n²) - Complejidad Cuadrática
Aquí empiezan los problemas de verdad. El tiempo de ejecución crece proporcionalmente al cuadrado de la entrada.
Ocurre, por ejemplo, cuando tenemos un bucle dentro de otro bucle (bucles anidados). Por cada elemento, recorres todos los demás.
- Si N = 10, operaciones ≈ 100
- Si N = 1.000, operaciones ≈ 1.000.000 😱
Ejemplo: Algoritmo de la burbuja (Bubble Sort) o comprobación de duplicados “fuerza bruta”.
// Comprobar duplicados (Enfoque ingenuo)
function tieneDuplicados(lista) {
for (let i = 0; i < lista.length; i++) { // Bucle externo (n)
for (let j = 0; j < lista.length; j++) { // Bucle interno (n)
if (i !== j && lista[i] === lista[j]) return true;
}
}
return false;
}
Evita los algoritmos O(n²) siempre que trabajes con conjuntos de datos medianos o grandes. Son la causa principal de cuellos de botella y timeouts en producción.
Comparativa en términos de tiempo
Para que veáis la importancia de la métrica, y la magnitud de la tragedia, vamos a verlo en un caso con tiempos (si, he dicho que no se medía en tiempos, pero para que lo entendamos más fácil)
Supón, en un determinado ordenador, cada operación tarda 1 milisegundo, y tenemos que procesar 10.000 datos.
| Notación | Nombre | Operaciones aprox. | Tiempo estimado |
|---|---|---|---|
| O(1) | Constante | 1 | 1 milisegundo |
| O(log(n)) | Logarítmica | 14 | 14 milisegundos |
| O(n) | Lineal | 10.000 | 10 segundos |
| O(n · log(n)) | Lineal-Logarítmica | 140.000 | 2 minutos |
| O(n²) | Cuadrática | 100.000.000 | 27 horas |
Fijaos bien. En este supuesto, la diferencia entre usar un algoritmo lineal O(n) y uno cuadrático O(n²) es la diferencia entre esperar 10 segundos o esperar más de un día.
Aquí se entiende bien porque hablamos de “el orden de”. Que con un cronómetro en mano, sean 1 o 5 milisegundos, o 22 o 27 horas, no tiene importancia.
La cuestión es que la diferencia relativa es tan enorme, que aunque uno fuera 5ms, y el otro 22 horas, iba a dar igual.
Más lento que “muy lento” (> n²)
¿Hay algo peor que O(n²)? Si, por supuesto que sí 😊. Más allá de la complejidad cuadrática entramos en lo que podríamos llamar la “Zona Intratable”:
- Polinomial superior (
, etc.): Tres o más bucles anidados. - Exponencial (
): Típico de recursividad sin optimizar. - Factorial (
): Generación de todas las permutaciones posibles.
Son órdenes de magnitud mucho peores. Si con el ejemplo anterior (N = 10.000) el algoritmo cuadrático tardaba 27 horas, estos algoritmos podrían tardar siglos o milenios en terminar.
En general, consideramos estos algoritmos inviables. Solo deberías usarlos si el tamaño de tus datos es minúsculo o si estás resolviendo problemas matemáticos muy específicos donde matemáticamente no existe otra solución (como el problema del viajante o criptografía).
