Complejidad de Algoritmos y Big O: ¿Qué tan rápido es tu código?
Cuando hablamos de algoritmos, una pregunta clave es: ¿qué tan eficientes son? Es acá donde entra el concepto de complejidad de algoritmo, que se mide con la notación Big O.
Imagina que tienes muchas formas de ordenar una lista de números. Aunque todas logran lo mismo, algunas requieren más pasos que otras. La complejidad algorítmica nos ayuda a comparar algoritmos y entender cómo su rendimiento se ve afectado cuando aumenta la cantidad de datos.
En esta lección, veremos qué significa Big O, cómo se mide la eficiencia de un algoritmo y por qué una solución más rápida no siempre es la mejor opción.
¿Qué es Big O?
Big O describe cómo crece el número de operaciones de un algoritmo a medida que aumenta la cantidad de datos de entrada (n). Su propósito es darnos una idea de la eficiencia de un algoritmo al enfrentarse a grandes volúmenes de datos.
Aquí tienes algunas de las notaciones más comunes:
- O(1) → Complejidad constante
- O(n) → Complejidad lineal
- O(n²) → Complejidad cuadrática
- O(log n) → Complejidad logarítmica
- O(n log n) → Complejidad lineal-logarítmica
O(1): Tiempo constante
Si una operación siempre toma la misma cantidad de tiempo, sin importar el tamaño de los datos, se dice que tiene una complejidad O(1).
function accederAPrimerElemento(array) {
return array[0]; // Solo una operación sin importar el tamaño del array
}
Acceder por índice a un array siempre toma el mismo tiempo, sin importar su tamaño.
O(n): Tiempo lineal
Si una función necesita recorrer todos los elementos de un array, su tiempo de ejecución crecerá proporcionalmente con el tamaño del array. Esto es O(n).
function imprimirElementos(array) {
for (let elemento of array) {
console.log(elemento);
}
}
Si el array tiene 10 elementos, el bucle se ejecuta 10 veces. Si tiene 1000, lo hace 1000 veces.
O(n²): Tiempo cuadrático
Los bucles anidados generan un incremento rápido en el número de operaciones. La búsqueda de elementos repetidos en dos arrays de tamaño n es un clásico ejemplo:
function encontrarInterseccion(arr1, arr2) {
let interseccion = [];
for (let i of arr1) {
if (arr2.includes(i)) { // includes() es O(n), y se ejecuta dentro de otro bucle O(n)
interseccion.push(i);
}
}
return interseccion;
}
Si cada array tiene 1000 elementos, el peor caso requeriría 1,000,000 comparaciones.
¿Siempre se usa el peor caso?
No siempre, pero en algoritmos se evalúa la peor situación posible para medir el rendimiento realista. Es como resolver un cubo de Rubik: algunos están casi listos con pocos movimientos, pero en el peor de los escenarios necesitarás muchos más.
Para la búsqueda en un array desordenado:
| Caso | Complejidad |
|---|---|
| Mejor caso | O(1) (el elemento está en la primera posición) |
| Peor caso | O(n) (se revisan todos los elementos) |
¿Más rápido significa mejor?
A veces, optimizar código termina haciendo que sea más difícil de leer y mantener. Donald Knuth, un famoso científico de la computación, decía:
"La optimización prematura es la raíz de todos los males".
En la práctica, la lentitud del código proviene, muchas veces, de accesos a base de datos o redes, no del algoritmo en sí. Optimizar demasiado temprano puede llevar a código innecesariamente complejo.
Por eso, lo importante es escribir código claro y fácil de entender, y solo optimizar cuando realmente sea necesario.
Resumen
- Big O mide el crecimiento del número de operaciones a medida que aumenta el tamaño de los datos.
- O(1) es constante, O(n) es lineal, O(n²) es cuadrático y O(log n) crece más lento que O(n).
- El peor de los casos nos ayuda a evaluar la eficiencia de un algoritmo.
- No siempre la solución más rápida es la mejor: código más eficiente puede ser más difícil de leer y mantener.
- Primero escribe código claro y funcional; optimiza solo si es necesario.
¡Ahora ya sabes cómo evaluar la eficiencia de tus algoritmos!
Materiales adicionales
Para acceder completo a curso necesitas un plan básico
El plan básico te dará acceso completo a todos los cursos, ejercicios y lecciones de Códica, proyectos y acceso de por vida a la teoría de las lecciones completadas. La suscripción se puede cancelar en cualquier momento.
