A lo largo del curso hemos ido dejando afirmaciones a cuenta: que anidar dos bucles cuadruplica el trabajo al doblar los datos (03-03), que la búsqueda binaria resuelve en veinte comparaciones lo que a la lineal le cuesta un millón (06-01), que sorted es 3.600 veces más rápido que nuestra burbuja (06-02) y que el Fibonacci ingenuo «explota» (06-03). Todas hablan de lo mismo: cuánto cuesta un programa según el tamaño de sus datos. Esta lección te da por fin el vocabulario para decirlo con precisión.

Ese vocabulario se llama notación Big-O, y es una de esas herramientas que cambian tu forma de mirar el código: en cuanto la tienes, puedes abrir una función que no has escrito tú y saber, sin ejecutarla, si aguantará mil datos o doscientos mil. También aprenderás lo contrario, que importa igual: cuándo no hay que optimizar nada.

1. Por qué no se mide en segundos
2. Qué se cuenta en su lugar
3. La notación Big-O y cómo se simplifica
4. Catálogo de complejidades
5. La tabla del crecimiento
6. Cómo analizar un fragmento de código
7. Tres fragmentos de TareaFácil analizados
8. Peor caso, mejor caso y caso medio
9. Complejidad en espacio y el intercambio tiempo-memoria
10. Coste de las operaciones habituales en Python
11. Cuándo optimizar y cuándo no
12. TareaFácil con 20 tareas y con 200.000
13. Errores comunes y consejos
14. Ejercicios
15. Conclusión del módulo

En 06-02 medimos la burbuja con time.perf_counter() y salieron 11 segundos para 10.000 elementos. Es un dato útil, pero no sirve para comunicar nada fuera de aquel momento concreto, porque depende de:

• La máquina: un portátil de hace ocho años y un servidor moderno difieren en un factor de diez.
• El lenguaje y su versión: la misma burbuja en C es unas cincuenta veces más rápida que en Python.
• Lo que estuviera haciendo el ordenador en ese instante: otro programa, el antivirus, el navegador.
• Los datos concretos que le tocaron: una lista casi ordenada o una del revés dan tiempos distintos.

Si te digo «mi función tarda 0,4 segundos», no sabes si es buena. Si te digo «mi función dobla su tiempo cada vez que dobla el número de tareas», ya sabes todo lo importante: sabes que con 200.000 tareas irá 10.000 veces más lenta que con 20, y eso es cierto en cualquier ordenador y en cualquier lenguaje.

Ese es el cambio de mentalidad: en vez de medir cuánto tarda, describimos cómo crece lo que tarda cuando crecen los datos. Es una propiedad del algoritmo, no de la máquina.

Se cuentan operaciones elementales en función del tamaño de la entrada, que por convenio se llama n. Una operación elemental es aquella cuyo coste no depende del tamaño de los datos: una suma, una comparación, una asignación, acceder a lista[i], llamar a una función.

Sumando: 1 + n + n + 1, es decir, 2n + 2 operaciones. Lo importante no es el número exacto —depende de cómo cuentes— sino la forma de la expresión: hay un término que crece con n y unos añadidos que no. Y lo primero que hay que entender es que n no es «cuántos datos hay» en abstracto, sino el tamaño de lo que hace crecer el trabajo: aquí, el número de tareas de la agenda.

La notación Big-O (o notación asintótica) describe cómo crece el número de operaciones cuando n se hace grande, ignorando todo lo que deja de importar a esa escala. Se escribe O(...) y se lee «del orden de».

Formalmente es una cota superior: decir que un algoritmo es O(n) significa que su coste no crece más rápido que n, salvo por un factor constante. Y de ahí salen las dos reglas de simplificación:

• Se ignoran las constantes multiplicativas. 3n y n son ambos O(n): un algoritmo tres veces más lento sigue doblando su tiempo al doblar los datos. La constante depende de la máquina; la forma de crecer, no.
• Se ignoran los términos menores. En n² + 500n + 1000, cuando n vale un millón, n² es un billón y 500n son quinientos millones: el segundo término es el 0,05 % del total. Se queda O(n²).

La consecuencia práctica de esta manga ancha es que Big-O no compara dos algoritmos con la misma forma: entre dos algoritmos O(n), uno puede ser cinco veces más rápido que el otro y Big-O no lo dirá. Para eso está time.perf_counter(). Big-O responde a otra pregunta, mucho más importante: ¿qué pasará cuando los datos crezcan?

Estas seis cubren prácticamente todo lo que te encontrarás, y de todas tienes ya un ejemplo en este curso:

Merece la pena detenerse en dos de ellas. O(1) no significa «rápido», significa «el mismo coste sea cual sea el tamaño»: acceder a lista[999999] cuesta lo mismo que a lista[0], porque Python calcula la dirección de memoria en vez de recorrer. Y O(log n) es casi tan bueno como O(1): el logaritmo en base 2 de un millón es 20, y el de mil millones es 30. Un algoritmo logarítmico apenas nota que los datos crezcan.

En el otro extremo, O(2ⁿ) es un muro: cada elemento nuevo duplica el trabajo total. Con n = 60 no hay ordenador en el mundo que termine, y por eso el Fibonacci ingenuo era inservible. Ordenados de mejor a peor:

Los números son más elocuentes que las curvas. Operaciones aproximadas para cada tamaño:

Traduzcamos la última fila a tiempo, suponiendo diez millones de operaciones por segundo, que es un orden de magnitud razonable para Python:

Ahí está toda la lección en una tabla. Con un millón de datos, un algoritmo O(n log n) responde mientras esperas y uno O(n²) no termina nunca en la práctica. Y fíjate en algo crucial: con n = 10 todos son instantáneos. La complejidad solo importa cuando los datos crecen, y esa observación será la sección 11.

Tres reglas prácticas bastan para el 95 % de los casos:

1. Instrucciones sueltas (asignaciones, comparaciones, accesos por índice o por clave): O(1).
2. Bucles secuenciales se suman; bucles anidados se multiplican. Dos bucles seguidos de n vueltas son n + n = 2n → O(n). Un bucle de n vueltas dentro de otro de n vueltas son n × n → O(n²).
3. Se toma el término dominante. Si un fragmento hace un sorted (O(n log n)) y luego un recorrido (O(n)), el total es O(n log n), porque manda el mayor.

El cálculo es 1 + n + n + n² = n² + 2n + 1, que se simplifica a O(n²). Y esta es la lección de diseño más rentable del análisis: el par de bucles anidados domina sobre todo lo demás. Optimizar los dos primeros bucles no serviría de nada; el único cambio que importa es eliminar el anidamiento, cosa que sabes hacer desde 06-01 con un índice.

Hay dos trampas frecuentes al analizar. La primera: una llamada a función tiene el coste de la función, no O(1). Si dentro de un bucle de n vueltas llamas a sorted sobre la agenda, el total es n × n log n, no n. La segunda: el operador in sobre una lista es O(n), así que un if x in lista dentro de un bucle es un bucle anidado disfrazado.

Fragmento 1: resumen_por_responsable (desde la v0.10), que cuenta las tareas de cada persona con un diccionario.

Un bucle de n vueltas con trabajo O(1) dentro: O(n). Es óptimo, porque para contar hay que mirar todas las tareas al menos una vez. La clave está en que conteo.get(...) sea O(1); si en vez de un diccionario usáramos una lista de nombres y un .index(), cada vuelta sería O(n) y el total O(n²).

Fragmento 2: mostrar_listado (v0.13), que ordena antes de imprimir.

sorted es O(n log n) y el recorrido es O(n); el término dominante manda: O(n log n). No se puede hacer mejor mientras haya que ordenar, y ese es el argumento honesto para no obsesionarse: la parte cara no es tu código, es la ordenación, y la ordenación ya la hace Timsort.

Fragmento 3: detectar títulos duplicados, escrito de la forma ingenua.

Bucles anidados: O(n²). Con 20 tareas son unas 190 comparaciones, nada. Con 200.000 serían veinte mil millones: horas de espera. La versión con conjunto, que ya sabes escribir desde 05-03, resuelve lo mismo en O(n):

Mismo resultado, un solo bucle. Este es el ejemplo perfecto de por qué la lección importa: el segundo código no es más listo, es más barato, y la diferencia solo se ve si sabes contar.

Un mismo algoritmo puede costar cosas muy distintas según los datos concretos que le toquen. Se distinguen tres escenarios, y ya los viste en la búsqueda lineal de 06-01:

Cuando alguien dice «este algoritmo es O(x)» sin precisar, se refiere al peor caso. Es la convención, y tiene una razón sólida: el peor caso es una garantía. Si el peor caso es O(n log n), sabes que jamás tardará más, pasen los datos que pasen. El caso medio es una expectativa, no una promesa, y hay algoritmos famosos —el quicksort de 06-02— con un caso medio excelente y un peor caso malo.

El tiempo no es lo único que se consume: también hay complejidad en espacio, que mide cuánta memoria extra necesita un algoritmo además de los datos de entrada.

Las dos últimas filas son el famoso intercambio tiempo-memoria: se gasta memoria para ganar tiempo. El caso de la memoización es demoledor: pasa Fibonacci de O(2ⁿ) a O(n) en tiempo, a cambio de O(n) en espacio. Es de los mejores negocios que existen en programación.

El índice invertido es el mismo trato en pequeño: indice_por_responsable cuesta O(n) construirlo y O(n) de memoria, y a cambio cada consulta «¿qué tiene Luis?» pasa de O(n) a O(1). Con una consulta no compensa; con quince al día, se paga solo. Y hay una tercera dimensión que el trato ignora y conviene no olvidar: el índice hay que mantenerlo actualizado, y ese coste es de mantenimiento del código, no de tiempo de ejecución.

Esta tabla es de las cosas más útiles que te llevarás del módulo. Con n = número de elementos:

Las filas en negrita son las que causan problemas reales. insert(0, x) y pop(0) son O(n) porque una lista guarda sus elementos consecutivos en memoria: meter o sacar por el principio obliga a desplazar todos los demás. Un bucle que hace pop(0) n veces es O(n²) sin que lo parezca. La solución de la biblioteca estándar es collections.deque, una lista doblemente enlazada donde ambos extremos son O(1).

Y x in lista es O(n) mientras que x in conjunto es O(1), que es la traducción a este vocabulario de todo lo que vimos en 06-01. Cambiar una lista por un conjunto es la optimización más barata y más rentable que existe: una línea de código y un cambio de complejidad.

Aquí llega la parte que casi nunca se cuenta, y es tan importante como el resto. La mayoría de las optimizaciones no hacen falta.

• Mientras n sea pequeño, la claridad manda. Con 20 tareas, un algoritmo O(n²) hace 400 operaciones: microsegundos. Reescribir ese código para hacerlo O(n) lo vuelve más difícil de leer a cambio de un ahorro que nadie percibirá.
• Mide antes de tocar. La intuición sobre dónde está la lentitud es notoriamente mala. Usa time.perf_counter() alrededor de los trozos sospechosos y descubre el cuello de botella en vez de suponerlo. En la mayoría de programas reales, el tiempo se va en la red o el disco, no en tu bucle.
• Optimiza la complejidad, no las constantes. Si hay que mejorar algo, pasar de O(n²) a O(n) cambiando una lista por un conjunto vale mil veces más que ahorrar tres operaciones dentro de un bucle.
• Pero elige bien desde el principio cuando es gratis. Escribir if x in conjunto en vez de if x in lista no cuesta esfuerzo extra ni legibilidad. Eso no es optimizar prematuramente: es no estropear el programa por descuido.

La regla que resume todo esto es de Donald Knuth y tiene medio siglo: la optimización prematura es la raíz de todos los males. Escribe código claro y correcto; mide; y optimiza solo lo que la medición señale. Big-O no está para que optimices todo, sino para que sepas qué va a pasar cuando los datos crezcan y detectes a tiempo lo que no aguantará.

Analicemos el programa entero, que va por la v0.14, en los dos escenarios.

Con 20 tareas, todo está bien y no hay nada que cambiar. Ese es el veredicto honesto, y no una concesión: el programa es claro, correcto y responde al instante. Optimizarlo sería trabajo desperdiciado.

Con 200.000 tareas, en cambio, el análisis dice exactamente qué tocar y en qué orden:

1. Eliminar cualquier O(n²), empezando por la detección de duplicados: la versión con conjunto de la sección 7 lo arregla en cuatro líneas. Es lo único verdaderamente urgente.
2. Construir el índice una sola vez al arrancar y mantenerlo al día en cada alta y cada baja, en lugar de reconstruirlo en cada consulta. Pasa las búsquedas por responsable de O(n) a O(1).
3. No ordenar la agenda entera para mostrar veinte líneas. Si el listado se pagina, heapq.nsmallest(20, agenda, key=clave_orden) es O(n log 20) en vez de O(n log n).
4. Dejar de cargar y guardar el fichero completo. Un JSON de 200.000 tareas se lee entero en memoria cada vez; a esa escala la respuesta no es un algoritmo mejor, es una base de datos, que indexa, busca y guarda solo lo que cambia.

Fíjate en el orden: primero se quitan las complejidades malas, después se aplican intercambios tiempo-memoria y solo al final se cambia de herramienta. Y fíjate en lo que no aparece: reescribir sorted, microoptimizar las f-strings o quitar funciones para ahorrar llamadas. Eso no movería la aguja.

Confundir «rápido» con «buena complejidad». Un algoritmo O(n²) bien escrito puede ganar a uno O(n log n) para n pequeño, porque las constantes que Big-O ignora existen de verdad. Timsort, sin ir más lejos, ordena los tramos cortos con inserción justo por eso.

Olvidar el coste de lo que se llama. if titulo in [t["titulo"] for t in agenda] parece una línea inocente y es O(n) cada vez: construye una lista entera y la recorre. Dentro de un bucle, O(n²).

Creer que O(1) significa instantáneo y O(n²) significa inaceptable. Son formas de crecer, no velocidades. O(n²) con n = 20 es perfecto; O(n) con una operación costosa dentro puede ser un desastre.

Analizar el mejor caso sin decirlo. «Mi búsqueda es O(1) porque normalmente está al principio» es una media verdad. Por convenio se habla del peor caso, que es el que da garantías.

Optimizar sin medir. Cambiar código «porque parece lento» suele empeorar la legibilidad sin mejorar el tiempo. Mide, localiza y entonces actúa.

Consejo: aprende a ver los bucles anidados. No siempre están indentados uno dentro de otro. Un in sobre una lista, un .index(), una comprensión o una llamada a otra función que recorre son bucles ocultos. Pregúntate siempre: ¿esta línea recorre algo?

Consejo: el mejor cambio suele ser de estructura de datos, no de algoritmo. Lista → conjunto para pertenencia; lista → diccionario para buscar por clave. Una línea, y la complejidad cae un escalón entero.

Indica la complejidad en tiempo de cada fragmento, en función de n = len(agenda), y justifica la respuesta en una frase.

Esta función comprueba qué tareas de una lista de encargos nuevos ya existen en la agenda. Di su complejidad, reescríbela para que sea O(n + m) (siendo m el número de encargos nuevos) e indica cuánta memoria extra gasta la nueva versión.

Escribe una función que mida con time.perf_counter() cuánto tarda x in lista frente a x in conjunto buscando un elemento que no está, para n = 10.000 y n = 100.000. Predice antes de ejecutar qué le pasará a cada tiempo al multiplicar n por diez, y comprueba si acertaste.

Solución 1.

El (b) es el caso más instructivo: no hay dos bucles indentados a la vista, pero la comprensión de dentro es el bucle interior. La versión correcta construye el conjunto de títulos una sola vez, fuera del bucle, y queda en O(n).

Solución 2.

La versión original es O(n × m): por cada encargo recorre la agenda entera. La reescritura cambia el bucle interior por un conjunto:

Construir el conjunto cuesta O(n) y la comprensión O(m), así que el total es O(n + m). Con 200.000 tareas y 100 encargos, se pasa de 20 millones de comparaciones a 200.100 operaciones: unas cien veces menos. El coste es O(n) de memoria extra —el conjunto de títulos—, y es el intercambio tiempo-memoria en su forma más limpia: una línea de más, un escalón de complejidad menos.

Solución 3.

La predicción es directa a partir de la tabla de la sección 10: in sobre una lista es O(n), así que al multiplicar n por diez el tiempo se multiplica por diez; sobre un conjunto es O(1), así que no cambia. Al ejecutarlo verás justo eso: la lista pasa de unas décimas de milisegundo a unos milisegundos, mientras que el conjunto se queda clavado en el orden de la millonésima de segundo, mida lo que mida. Buscar el elemento ausente es deliberado: es el peor caso de la lista, que obliga a recorrerla entera, y en el conjunto no cambia nada. Guarda este experimento: es la demostración práctica de todo el módulo en veinte líneas.

La eficiencia no se mide en segundos porque los segundos dependen de la máquina, del lenguaje y de la suerte. Se describe contando operaciones elementales en función de n y quedándose con cómo crecen: eso es la notación Big-O, una cota superior en la que se ignoran las constantes multiplicativas y los términos menores, de modo que 3n + 5 es O(n) y n² + 500n es O(n²). El catálogo cabe en una línea —O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)— y todas tienen su ejemplo en este curso, desde el acceso a un diccionario hasta el Fibonacci ingenuo. Para analizar código bastan tres reglas: las instrucciones sueltas son O(1), los bucles secuenciales se suman y los anidados se multiplican, y manda el término dominante. Por convenio se habla del peor caso, porque es el único que ofrece garantías. Y junto al tiempo está la complejidad en espacio, con su intercambio tiempo-memoria: memoización e índices invertidos gastan O(n) de memoria para rebajar el tiempo un escalón entero. La tabla de costes de listas, diccionarios y conjuntos —con in en O(n) frente a O(1), y los insert(0, x) y pop(0) que son O(n) sin parecerlo— es la chuleta que usarás a diario. Pero la conclusión más importante es la contraria: mientras n sea pequeño, la claridad manda; mide antes de tocar y optimiza solo lo que la medición señale.

Con esto se cierra el módulo 6, y con él las cajas negras que arrastrábamos. Sabes buscar: linealmente con salida temprana, binariamente descartando mitades sobre datos ordenados y por clave gracias a la tabla hash, además de preparar índices invertidos cuando una consulta se repite. Sabes ordenar: selección, inserción y burbuja con su centinela, la diferencia entre estable e inestable, la estrategia de división que hay detrás de mergesort y quicksort, y el uso profesional de sorted/.sort() con key, reverse y tuplas para varios criterios. Sabes usar la recursión con su caso base y su caso recursivo, reconocer cuándo gana —datos con forma de árbol, algoritmos que dividen— y arreglar su trabajo repetido con memoización. Y ahora sabes decir cuánto cuesta todo eso. TareaFácil ha llegado a la v0.14: busca, ordena por dos criterios, reparte el plan de mañana y suma proyectos desglosados a cualquier profundidad.

Y sin embargo, mira lo que sostiene todo eso: una lista de diccionarios. Nada impide que a un diccionario le falte la clave completada, que otro tenga prioridad escrita como "Alta", o que un tercero arrastre un campo inventado que nadie más entiende; el programa no protestará hasta que reviente por un KeyError a mitad del listado. Y las funciones que operan sobre tareas —mostrar_ficha, dias_totales, clave_orden— están sueltas por el fichero, separadas de los datos que manipulan, sin nada que diga que forman un conjunto. En De los datos a los objetos: clases e instancias empieza el módulo 7, donde datos y comportamiento dejan de ir por separado: aprenderás a definir qué es exactamente una tarea, garantizar que todas nacen completas y guardar junto a ellas las operaciones que les pertenecen.