En la lección anterior aprendimos a expresar costes con la notación asintótica; en esta aprenderemos a calcularlos. El análisis de complejidad es la habilidad de mirar un algoritmo —o directamente su código— y determinar, sin ejecutarlo, cómo crecerán su tiempo y su memoria con el tamaño de la entrada. Es una habilidad de ingeniería de primer orden: permite descartar diseños inviables antes de escribir una línea y localizar cuellos de botella leyendo código.

Seguimos con Rutalia. Su equipo ha heredado un backend con funciones que "de repente" van lentas ahora que hay un millón de pedidos: buscar un pedido por identificador, detectar pedidos duplicados, registrar entregas en una lista que crece sin parar. En esta lección analizaremos esas funciones una a una y pondremos números a la intuición.

1. Complejidad temporal y espacial: qué medimos exactamente
2. Conteo de operaciones y reglas básicas
3. Bucles: simples, anidados y dependientes
4. Mejor caso, peor caso y caso medio
5. Análisis amortizado: la lista dinámica
6. Recurrencias y teorema maestro (introducción)

Dado un algoritmo y una entrada de tamaño n, definimos:

• Complejidad temporal T(n): número de operaciones elementales (en el modelo RAM de la lección 01-01) que ejecuta el algoritmo.
• Complejidad espacial S(n): cantidad de memoria adicional que necesita, sin contar la entrada. También se llama espacio auxiliar.

Un matiz que suele pasarse por alto: el espacio auxiliar incluye también la pila de llamadas de las funciones recursivas (cada llamada pendiente ocupa memoria). Lo veremos en detalle en la lección 01-03.

A menudo tiempo y espacio se intercambian: gastar más memoria (por ejemplo, un índice auxiliar) puede reducir drásticamente el tiempo. Gran parte de la ingeniería de algoritmos consiste en elegir bien ese equilibrio.

El método fundamental es directo: para cada línea, determinar (a) cuánto cuesta ejecutarla una vez y (b) cuántas veces se ejecuta. El coste total es la suma de todos los productos. Después se simplifica con la notación asintótica.

Analicemos la búsqueda lineal de un pedido en Rutalia:

Conteo en el peor caso (el pedido no está): el bucle da n vueltas con un coste constante c por vuelta, más un coste constante final. T(n) = c·n + c' = Θ(n). Espacio auxiliar: solo la variable del bucle → S(n) = Θ(1).

Reglas de composición que usaremos constantemente:

• Secuencia: bloques consecutivos se suman. Θ(n) + Θ(n²) = Θ(n²) (domina el mayor).
• Bucle: coste del cuerpo multiplicado por el número de iteraciones.
• Condicional: en el peor caso, el coste de la rama más cara (más la condición).
• Llamada a función: el coste de la función llamada (¡no cuesta 1 por ser una línea!).

Y el recordatorio de la lección anterior: en Python, x in lista es Θ(n), lista.insert(0, x) es Θ(n), sorted(lista) es Θ(n log n), un slice lista[a:b] es Θ(b−a). Contar "líneas" en lugar de operaciones reales es la fuente clásica de análisis erróneos.

Un bucle que da n vueltas con cuerpo constante es Θ(n). Si el cuerpo cuesta f(n), el total es n · f(n).

Los costes se multiplican. Versión ingenua del detector de pedidos duplicados de Rutalia (dos clientes que piden lo mismo a la misma dirección):

El bucle interior no da siempre n vueltas: da n−1 la primera vez, n−2 la segunda… Es un bucle dependiente (depende de i). El total de iteraciones es:

(n−1) + (n−2) + ... + 1 + 0 = n(n−1)/2 = Θ(n²)

Esta suma aritmética aparece constantemente; conviene memorizar el resultado: un doble bucle triangular es cuadrático, igual que el doble bucle completo n·n (la mitad de trabajo no cambia el orden). Con un millón de pedidos: ~5·10¹¹ comparaciones. Este es, literalmente, el proceso que tardaba horas en Rutalia.

La alternativa con memoria auxiliar:

Tiempo Θ(n) a cambio de espacio auxiliar Θ(n): un intercambio tiempo/memoria de manual. (Por qué el dict consigue O(1) por operación lo veremos en la lección 01-04.)

Cuando la variable de control se multiplica o divide en cada vuelta, el número de iteraciones es logarítmico:

Resumen de patrones:

Para un mismo n, distintas entradas pueden costar distinto. Definimos tres funciones:

• Peor caso T_peor(n): máximo coste sobre todas las entradas de tamaño n. Es la métrica por defecto: da una garantía.
• Mejor caso T_mejor(n): mínimo coste. Casi nunca es útil por sí solo (cualquier algoritmo con salida anticipada tiene mejor caso bueno).
• Caso medio T_medio(n): coste esperado bajo una distribución de entradas. Es el más realista y el más difícil: exige asumir una distribución.

Para buscar_pedido (búsqueda lineal), suponiendo que el pedido buscado está y es igualmente probable que esté en cualquier posición:

Fíjate: el caso medio sigue siendo lineal; "de media miro la mitad de la lista" no cambia el orden de crecimiento. Y recuerda la advertencia de 01-01: mejor/peor/medio son funciones distintas, y a cada una se le pueden aplicar O, Ω o Θ. "El peor caso de la búsqueda lineal es Θ(n)" es una afirmación completa y correcta.

En Rutalia esto tiene una lectura operativa: para el cuadro de mandos interno puede bastar un buen caso medio; para el cálculo de rutas que debe responder antes de que salgan las furgonetas a las 8:00, lo que importa es la garantía del peor caso.

Hay estructuras cuyas operaciones son casi siempre baratas pero de vez en cuando caras. Juzgarlas por su peor caso puntual es engañoso; lo honesto es repartir el coste: eso es el análisis amortizado. El coste amortizado de una operación es el coste total de una secuencia de m operaciones dividido entre m.

El ejemplo canónico es la lista dinámica —exactamente lo que hace list.append de Python—. Rutalia registra cada entrega del día en una lista:

Internamente, la lista reserva un array con cierta capacidad. Mientras queda hueco, append escribe en la siguiente posición: coste 1. Cuando el array se llena, se reserva otro (típicamente del doble de tamaño), se copian los k elementos existentes y luego se escribe: coste k+1.

¿Cuánto cuestan n appends empezando de vacío, con duplicación de capacidad? Las copias ocurren al llenar capacidades 1, 2, 4, 8, …, y copian ese número de elementos:

coste total ≤ n (escrituras) + (1 + 2 + 4 + ... + n) (copias) ≤ n + 2n = 3n

Por tanto el coste amortizado por append es 3n / n = 3 = Θ(1), aunque un append concreto pueda costar Θ(n). Esta es la técnica agregada; existen otras más finas (método del banquero, del potencial) que no necesitaremos en este curso.

Dos consecuencias prácticas para Rutalia:

• Registrar el millón de entregas del día con append cuesta Θ(n) en total: perfecto.
• Cuidado con la operación "prima": entregas.insert(0, x) (insertar al principio) desplaza todos los elementos y cuesta Θ(n) cada vez, no amortizado. Un millón de inserciones al principio es Θ(n²). Si se necesita insertar por ambos extremos, la estructura adecuada es otra (collections.deque, que aparecerá en la lección 01-04).

Cuando un algoritmo se resuelve llamándose a sí mismo sobre entradas más pequeñas, su coste se expresa como una recurrencia: una ecuación donde T(n) depende de T sobre tamaños menores. Aquí solo necesitamos lo justo para analizar algoritmos de divide y vencerás; el diseño de algoritmos recursivos como técnica es el tema de la lección 01-03.

Ejemplo: Rutalia guarda las direcciones de entrega ordenadas alfabéticamente y busca con el clásico "abrir por la mitad" (la búsqueda binaria en sí se estudia a fondo en 04-01; aquí solo nos interesa su coste). Cada paso descarta la mitad de las direcciones con un trabajo constante:

T(n) = T(n/2) + c

Desplegando: T(n) = T(n/4) + 2c = T(n/8) + 3c = ... = T(1) + c·log₂ n = Θ(log n).

Para las recurrencias del tipo divide y vencerás existe una receta general, el teorema maestro. Para recurrencias de la forma:

T(n) = a · T(n/b) + f(n) con a ≥ 1 subproblemas de tamaño n/b y coste f(n) de dividir/combinar

se compara f(n) con n^(log_b a):

Comprobaciones rápidas:

• Búsqueda binaria: a=1, b=2 → n^(log₂ 1) = n⁰ = 1; f(n)=Θ(1) coincide → caso 2 → Θ(log n). ✔
• Ordenación por mezcla (que veremos como esquema en 01-03 y en detalle en 04-02): a=2, b=2, f(n)=Θ(n) → n^(log₂ 2) = n coincide → caso 2 → Θ(n log n). ✔

A nivel introductorio basta con esto: identificar a, b y f(n), calcular n^(log_b a) y elegir el caso. Cuando la recurrencia no encaje en el patrón (por ejemplo T(n) = T(n−1) + n, que da Θ(n²)), siempre queda el método de desplegar la recurrencia a mano, como hicimos con la búsqueda binaria.

• Contar líneas en lugar de operaciones. Una línea con sorted(...), in lista o un slice esconde costes Θ(n log n) o Θ(n). Antes de contar, pregúntate qué hace por dentro cada expresión.
• Multiplicar bucles anidados a ciegas. Si el bucle interior depende del exterior, hay que sumar la serie. A veces la suma da menos de lo esperado: dos bucles anidados donde el interior avanza un puntero global (patrón "dos punteros") pueden ser Θ(n) en total, no Θ(n²).
• Confundir amortizado con caso medio. El coste amortizado es una garantía sobre cualquier secuencia de operaciones (no hay probabilidad); el caso medio depende de una distribución de entradas supuesta. append es O(1) amortizado siempre; la búsqueda lineal es Θ(n) en media si la posición es uniforme.
• Olvidar el espacio. Un algoritmo elegante en tiempo puede ser inviable por memoria (p. ej. materializar todos los pares de pedidos: Θ(n²) de espacio con n = 10⁶ es del orden de terabytes). Analiza siempre ambas dimensiones.
• Aplicar el teorema maestro donde no toca. Requiere subproblemas de tamaño n/b (fracción constante). T(n) = T(n−1) + c no es divide y vencerás; se despliega a mano (da Θ(n)).
• Consejo: verifica empíricamente. Mide el tiempo con time.perf_counter() para n, 2n y 4n: si el tiempo se multiplica por ~4 al duplicar n, tienes algo cuadrático delante. La medición no sustituye al análisis, pero lo confirma o lo desmiente en minutos.

Determina la complejidad temporal (peor caso, en Θ) de cada función, justificando el conteo:

La función siguiente comprueba si un código de descuento está en la lista de códigos válidos (no ordenada, sin duplicados, n códigos). Suponiendo que cuando el código es válido su posición es uniforme al azar, y que el 50 % de las comprobaciones son de códigos inválidos, calcula mejor caso, peor caso y caso medio.

Resuelve con el teorema maestro (o desplegando, si no aplica):

1. T(n) = 4·T(n/2) + n
2. T(n) = T(n/2) + n
3. T(n) = T(n−1) + c

Solución 1

• a: dos bucles Θ(n) en secuencia (no anidados): Θ(n) + Θ(n) = Θ(n).
• b: la trampa está en resultado = resultado + [p], que crea una lista nueva copiando los k elementos acumulados: coste Θ(k) en la vuelta k. En el peor caso (todos urgentes): 1 + 2 + ... + n = Θ(n²). Con resultado.append(p) (amortizado O(1)) sería Θ(n). Una sola línea marca la diferencia entre 0,01 s y horas con un millón de pedidos.
• c: bucles anidados independientes: z vueltas × n vueltas de trabajo constante = Θ(z·n). Con dos variables de tamaño, la respuesta debe incluir ambas; decir "Θ(n²)" sería incorrecto salvo que z ≈ n.

Solución 2

• Mejor caso: el código es el primero → Θ(1).
• Peor caso: código inválido (o el último) → n comparaciones → Θ(n).
• Caso medio: con probabilidad 1/2 el código es inválido (n comparaciones); con probabilidad 1/2 es válido y en media mira (n+1)/2. Coste medio = ½·n + ½·(n+1)/2 = 3n/4 + 1/4 → Θ(n). Como siempre en búsqueda lineal, el caso medio no baja del orden lineal.

Solución 3

1. a=4, b=2, f(n)=n. n^(log₂ 4) = n², y f(n)=n crece menos → caso 1 → Θ(n²).
2. a=1, b=2, f(n)=n. n^(log₂ 1) = 1, y f(n)=n crece más (y cumple la regularidad) → caso 3 → Θ(n). Intuición: el primer nivel ya cuesta n, y los siguientes n/2, n/4… suman menos que 2n.
3. No aplica el teorema maestro (el subproblema es n−1, no una fracción de n). Desplegando: c + c + ... + c, n veces → Θ(n).

Ya sabemos calcular costes: contar operaciones línea a línea, componer secuencias (sumar) y bucles (multiplicar, o sumar la serie si son dependientes), distinguir mejor/peor/caso medio según la garantía que necesitemos, repartir costes puntuales caros mediante el análisis amortizado (la lista dinámica como ejemplo estrella) y resolver recurrencias de divide y vencerás con el teorema maestro. Aplicado a Rutalia, el diagnóstico es claro: el detector de duplicados cuadrático era el proceso de horas, y un intercambio tiempo/memoria lo baja a segundos.

En el análisis de recurrencias ha aparecido un protagonista que aún no hemos estudiado como merece: los algoritmos que se llaman a sí mismos. En la próxima lección, Recursión y Programación Dinámica, aprenderemos a diseñar recursiones correctas (caso base, avance, pila de llamadas), a usar divide y vencerás como esquema general y a rescatar las recursiones que repiten trabajo mediante memoización y programación dinámica — con un problema de reparto de Rutalia sobre la cuadrícula de la ciudad como hilo práctico.