Qué es un algoritmo y la notación Big-O explicada paso a paso

Empezamos por aprender a medir

Bienvenido a la serie de Algoritmos. Si vienes de los Fundamentos, ya sabes escribir programas que funcionan. Ahora toca el siguiente paso: que funcionen bien. Y para eso, lo primero de todo es aprender a medir.

¿Por qué empezar midiendo? Porque casi cualquier problema se puede resolver de varias formas, y unas son ridículamente mejores que otras. Pero “mejor” no es una opinión: se mide. Y la regla con la que se mide la eficiencia de un algoritmo se llama notación Big-O. Es lo que da nombre a esta primera entrega, y lo que vas a usar el resto de tu vida programando.

Qué es un algoritmo, en serio

Antes de medirlo, definámoslo. Un algoritmo es, simplemente, una secuencia finita de pasos bien definidos para resolver un problema. Ya lo viste en Fundamentos sin ponerle el nombre: la receta para hacer un café era un algoritmo.

Para ser un algoritmo de verdad, esa secuencia tiene que cumplir un par de cosas: ser finita (termina en algún momento, no se queda dando vueltas para siempre) y estar bien definida (cada paso es claro y no ambiguo). Una receta de cocina es un algoritmo. Las instrucciones de montar un mueble, también. Y ordenar una lista de números, igual.

Lo interesante es que para un mismo problema (por ejemplo, ordenar) hay muchos algoritmos distintos. Y aquí es donde entra la pregunta del millón: ¿cuál uso? Para responder, hay que medir dos cosas.

Las dos cosas que se miden: tiempo y espacio

Cuando medimos un algoritmo, no miramos los segundos del reloj. Esos dependen de tu ordenador, de si es nuevo o viejo, de si tienes mil pestañas abiertas. Lo que medimos es algo más profundo: cómo crece el trabajo cuando crecen los datos. Y hay dos magnitudes:

Complejidad temporal: cuántas operaciones hace el algoritmo según la cantidad de datos. Es la que más mira todo el mundo.
Complejidad espacial: cuánta memoria extra necesita según la cantidad de datos.

A la cantidad de datos la llamamos n. Si ordenas una lista de mil elementos, n vale mil. La pregunta clave siempre es la misma: cuando n crece, ¿cómo crece el trabajo? ¿Se mantiene igual? ¿Crece a la par? ¿Se dispara? Esa relación es lo que captura la Big-O.

La notación Big-O: cómo se lee

La Big-O describe el peor caso de cómo crece un algoritmo, ignorando los detalles que no importan a lo grande. Se escribe O() con la fórmula del crecimiento dentro. Vamos de la mejor a la peor, que es como conviene tenerlas en la cabeza:

O(1): tiempo constante. El santo grial. Tarde lo que tarde, no depende de n. Acceder al elemento de una lista por su índice es O(1): da igual que la lista tenga diez elementos o diez millones, llegar al de la posición 5 cuesta lo mismo.
O(log n): logarítmico. Crece despacísimo. Cada vez que doblas los datos, solo añades un paso más. Es lo que consigue la búsqueda binaria: buscar en una lista ordenada de un millón de elementos cuesta unos veinte pasos. Veinte. Es casi magia.
O(n): lineal. El trabajo crece a la par que los datos. El doble de datos, el doble de trabajo. Recorrer una lista entera para buscar algo es O(n): si hay n elementos, en el peor caso miras los n.
O(n log n): el bueno de ordenar. Un poco peor que lineal, pero es lo mejor que se puede hacer para ordenar comparando elementos. Lo veremos con merge sort y quick sort.
O(n²): cuadrático. Aquí empiezan los problemas. El doble de datos, el cuádruple de trabajo. Suele aparecer cuando tienes un bucle dentro de otro recorriendo los mismos datos. Aguanta con pocos datos, pero con muchos se ahoga.
O(2^n): exponencial. El infierno. Cada dato nuevo dobla el trabajo. Con 30 datos ya hablamos de mil millones de operaciones. Estos algoritmos son inviables salvo para entradas minúsculas, y evitarlos es justo el objetivo de técnicas como la programación dinámica.

De la mejor a la peor, en el orden en que conviene tenerlas en la cabeza.

Un ejemplo que lo deja claro

Imagina que tienes una guía telefónica (sí, de papel) con un millón de nombres ordenados alfabéticamente, y quieres encontrar a “Marcos”.

A lo bestia (O(n)): empiezas por la primera página y vas nombre a nombre. En el peor caso, un millón de comprobaciones.
Como una persona normal (O(log n)): abres por la mitad, ves si “Marcos” va antes o después, te quedas con esa mitad y repites. Cada paso descarta la mitad de la guía. Resultado: unos veinte pasos para un millón de nombres.

Un millón de pasos contra veinte. Mismo problema, mismos datos, y una diferencia de cincuenta mil veces. Eso es lo que mide la Big-O, y por eso importa tanto. No es teoría de pizarra: es la diferencia entre una app que responde al instante y otra que se cuelga.

Mejor, peor y caso promedio

Un detalle importante: un algoritmo no siempre tarda lo mismo. Por eso se habla de tres casos:

Mejor caso: cuando todo sale de cara. Buscas a “Aaron” y está el primero.
Peor caso: cuando todo sale fatal. Buscas a alguien que no está, y recorres todo.
Caso promedio: lo que pasa de media, que suele ser lo más realista.

Por convención, cuando alguien dice “este algoritmo es O(n)” suele referirse al peor caso, porque es la garantía: “no va a ir peor que esto”. Es lo prudente. Prometer por el mejor caso es como vender un coche por la velocidad que alcanza cuesta abajo.

Verás también las notaciones Big-Theta (Θ) y Big-Omega (Ω): la Omega es el mejor caso (la cota inferior) y la Theta es cuando el mejor y el peor coinciden (la cota ajustada). En el día a día, el 90% de las veces se habla de Big-O y del peor caso, así que no te agobies con las otras dos de momento.

Por qué esto cambia tu forma de programar

Cuando interiorizas la Big-O, dejas de escribir lo primero que se te ocurre. Empiezas a preguntarte, casi sin pensar, “¿esto escala?”. Ves un bucle dentro de otro y te suena la alarma del O(n²). Eliges una tabla hash en vez de una lista porque sabes que buscar te va a costar O(1) en lugar de O(n).

Y, muy práctico: media entrevista técnica consiste en que te pregunten “¿y cuál es la complejidad de tu solución?”. Saber responder eso, con soltura, es lo que te separa del montón.

El libro para esta entrega

Para toda la serie, y muy en especial para entender la Big-O sin agobios, mi recomendación es Comprender los algoritmos, de Aditya Bhargava. Empieza justo por aquí, por medir, y lo hace con dibujos y ejemplos en lugar de fórmulas. En español, que en este mundillo se agradece. Es el que iré recomendando a lo largo de la serie.

Lo siguiente: buscar bien

Ya sabes medir. Vamos a estrenar la herramienta con el problema más básico de todos: buscar algo en una colección. En la próxima entrega comparamos la búsqueda lineal contra la binaria, y verás en acción esa diferencia brutal entre O(n) y O(log n) que acabo de contarte con la guía telefónica.

Preguntas frecuentes

¿Qué significa la n en la notación Big-O?

La n representa el tamaño de la entrada, es decir, la cantidad de datos con los que trabaja el algoritmo. Si ordenas una lista de mil elementos, n vale mil. La notación Big-O describe cómo crece el trabajo del algoritmo cuando n crece: si se mantiene constante (O(1)), proporcional (O(n)), o se dispara (O(n²)). Lo que importa no es el número exacto de operaciones, sino cómo escala con n.

¿Por qué se mide el peor caso y no el promedio?

Porque el peor caso es una garantía: te asegura que el algoritmo nunca irá peor que eso, pase lo que pase con los datos. Es la información más útil para decidir si un algoritmo es seguro de usar a gran escala. El caso promedio también es valioso y a veces se analiza, pero cuando alguien dice “esto es O(n)” sin más, casi siempre se refiere al peor caso.

¿Es lo mismo O(n) que tardar n segundos?

No. La Big-O no mide segundos ni depende de tu ordenador, mide cómo crece el número de operaciones según los datos. Un algoritmo O(n) hace un trabajo proporcional a n, pero los segundos reales dependen de la máquina, el lenguaje y mil factores más. Por eso la Big-O es tan útil: compara algoritmos de forma justa, sin importar dónde se ejecuten.

Este artículo contiene enlaces de afiliado.

Compártelo si te ha resultado útil.

¿Qué te ha sorprendido más, lo de los veinte pasos para un millón de nombres? Cuéntame.

Y… en la próxima entrega, a buscar.