Empieza el entrenamiento. En esta lección no hay teoría nueva: hay una batería de ejercicios que ejercita todo el Módulo 2 —análisis temporal (02-01), análisis espacial (02-02) y casos mejor/peor/promedio (02-03)— usando la notación asintótica del Módulo 1 (01-03). Todos los ejercicios trabajan sobre código de RutaBus, nuestra aplicación de movilidad urbana.

Cómo trabajar esta lección: intenta cada ejercicio en papel antes de mirar la solución. En serio. Leer una solución de análisis de complejidad produce la sensación de "esto ya lo sé"; derivarla tú mismo es lo que construye el reflejo. Si te atascas más de diez minutos, lee la pista (si la hay) y vuelve a intentarlo antes de rendirte.

1. Derivar Θ de bucles simples, anidados y dependientes.
2. Los costes ocultos de Python: in sobre lista e insert(0).
3. Complejidad espacial: auxiliar frente a total, y recursión con slices frente a índices.
4. Mejor, peor y caso promedio de una función de validación.
5. Emparejar cada código con su orden de crecimiento a partir de mediciones.
6. Detecta el coste oculto: la función que parece lineal pero no lo es.

Dificultad: básica

RutaBus registra cada fichaje como una tupla (hora, parada, linea). Analiza estas tres funciones y deriva la complejidad temporal Θ de cada una en función de n (el tamaño de la lista de entrada). Para la tercera, calcula además el número exacto de iteraciones del bucle interno.

contar_fichajes_linea: un solo bucle que recorre los n fichajes haciendo trabajo O(1) en cada vuelta (una comparación y, a veces, una suma). Como vimos en 02-01, el coste es proporcional al número de iteraciones: Θ(n). Fíjate en que el if no cambia el orden: se ejecute o no el cuerpo, la comparación se hace siempre.

matriz_coincidencias: dos bucles anidados independientes (el rango de j no depende de i): n · n iteraciones con trabajo O(1) cada una. La creación previa de la matriz también cuesta Θ(n²), pero no cambia el total: Θ(n²).

pares_conflictivos: aquí el bucle interno depende de i. Contemos las iteraciones exactas: para i = 0 hay n−1, para i = 1 hay n−2, …, para i = n−1 hay 0. La suma es:

(n−1) + (n−2) + … + 1 + 0 = n(n−1)/2

Como vimos en 02-01, n(n−1)/2 = n²/2 − n/2, y al simplificar (01-03) descartamos constantes y términos menores: Θ(n²). El bucle dependiente hace la mitad de trabajo que el independiente, pero la mitad de un cuadrático sigue siendo cuadrático.

Errores típicos: (1) pensar que el bucle dependiente es "algo intermedio" tipo O(n log n) — no: la serie aritmética da cuadrático; (2) sumar Θ(n²) + Θ(n²) de la creación de la matriz y decir Θ(2n²) — las constantes se descartan.

Dificultad: media

El equipo de datos de RutaBus escribió estas dos funciones. Deriva su coste temporal real. Llama n al número de fichajes/avisos, m al tamaño de paradas_conocidas y k al número de paradas nuevas encontradas.

Preguntas: (a) ¿cuál es el coste de cada comprobación marcada?; (b) ¿cuál es el coste total de cada función?; (c) ¿qué pasa con paradas_nuevas en el peor caso en que todas las paradas son nuevas?

Pista: repasa la tabla de costes ocultos de 02-01: x in lista no cuesta lo mismo que x in conjunto, y las listas de Python están optimizadas para tocar su final, no su principio.

(a) Como vimos en 02-01, parada not in paradas_conocidas sobre una lista es una búsqueda lineal: O(m). La segunda comprobación, parada not in nuevas, cuesta O(k) donde k es el tamaño actual de nuevas. Y resultado.insert(0, aviso) desplaza todos los elementos existentes una posición: O(longitud actual).

(b) paradas_nuevas hace n iteraciones y en cada una paga O(m) + O(k): total O(n·(m + k)). ultimos_primero paga 0 + 1 + 2 + … + (n−1) = n(n−1)/2 desplazamientos: Θ(n²) — la misma serie aritmética del Ejercicio 1, esta vez escondida dentro de un método.

(c) Si todas las paradas son nuevas, k crece hasta n y el coste se convierte en O(n·m + n²): la función que "parecía" un filtrado lineal es cuadrática.

Para que conste (la reparación se practica en 06-03, aquí solo diagnosticamos): la comprobación sería O(1) con un set, y ultimos_primero sería Θ(n) con append + reverse() (o directamente avisos[::-1]).

Error típico: contar cada línea de Python como "una operación". La línea if parada not in paradas_conocidas: es una línea, pero son m comparaciones. El análisis línea a línea de 02-01 exige conocer el coste real de cada operación, no su longitud tipográfica.

Dificultad: media

Dos versiones recursivas de la suma de ocupación de un trayecto (lista de pasajeros por tramo):

Preguntas: (a) espacio auxiliar de cada versión; (b) espacio total; (c) complejidad temporal de cada una; (d) ¿qué ocurre en la práctica al llamarlas con una lista de 10 000 tramos?

(a) Espacio auxiliar. Ambas versiones hacen n+1 llamadas anidadas, así que ambas pagan una pila de profundidad Θ(n) (02-02: cada marco de la pila cuenta como espacio auxiliar). Pero la versión con slice paga además una copia por llamada: ocupacion[1:] crea una lista nueva de n−1 elementos, la siguiente llamada crea otra de n−2, etc. Y aquí está lo importante: mientras la recursión está en su punto más profundo, todas esas copias están vivas a la vez (cada una es argumento de un marco que aún no ha retornado). Total: (n−1) + (n−2) + … + 1 ≈ n²/2 → espacio auxiliar Θ(n²). La versión con índices no copia nada: solo la pila, Θ(n) auxiliar.

(b) Espacio total = entrada + auxiliar (02-02). Con slice: Θ(n) + Θ(n²) = Θ(n²). Con índices: Θ(n) + Θ(n) = Θ(n).

(c) Tiempo. El slice no solo ocupa: también tarda O(longitud) en copiarse (02-01). La versión slice paga la misma serie aritmética en tiempo: Θ(n²). La versión con índices: Θ(n).

(d) Ninguna de las dos sobrevive a 10 000 elementos: Python limita la profundidad de recursión a ~1000 por defecto, así que ambas lanzan RecursionError mucho antes de que la memoria sea el problema. Como vimos en 01-02 al comparar iterativo y recursivo, cuando la recursión es puramente lineal, un bucle (o sum(ocupacion)) hace el mismo trabajo con pila O(1).

Errores típicos: (1) olvidar que el slice copia (parece un acceso, pero es una lista nueva); (2) contar solo "un marco de pila" en lugar de la profundidad máxima simultánea; (3) confundir espacio auxiliar con total y reportar Θ(n²) para la versión con índices "porque la entrada más la pila suman mucho" — la entrada es Θ(n) y la pila Θ(n): total Θ(n).

Dificultad: media

En cada fichaje, RutaBus valida el billete contra la lista de billetes activos:

Los datos de explotación dicen que el 90 % de los fichajes son válidos, y que los billetes válidos aparecen en posiciones uniformemente distribuidas de la lista. El 10 % restante son billetes inválidos (no están en la lista).

Preguntas: (a) mejor caso y peor caso, con la notación adecuada; (b) número esperado de comparaciones con esa distribución, y el Θ del caso promedio; (c) si el porcentaje de inválidos subiera al 99 %, ¿cambiaría el Θ del promedio?

(a) Mejor caso: el billete es el primero de la lista → 1 comparación → Θ(1). Peor caso: el billete es el último o no está → n comparaciones → Θ(n). Fíjate en que usamos Θ del caso, como precisamos en 02-03: cada caso tiene su cota ajustada.

(b) Es exactamente el esquema de la búsqueda lineal de 02-03, pero con la distribución dada. Si el billete es válido y está en posición uniforme, el número medio de comparaciones es (1 + 2 + … + n)/n = (n+1)/2. Si es inválido, siempre son n. Esperanza total:

E[comparaciones] = 0,9 · (n+1)/2 + 0,1 · n = 0,45n + 0,45 + 0,1n = 0,55n + 0,45

Eso es Θ(n): una recta con pendiente 0,55, pero recta al fin y al cabo.

(c) Con 99 % de inválidos: E = 0,01 · (n+1)/2 + 0,99 · n ≈ 0,995n. La constante casi se duplica respecto al caso anterior (0,55 → 0,995), lo que en producción se nota, pero el Θ no cambia: sigue siendo Θ(n). Esta es la lección de 02-03: la distribución de entradas mueve las constantes del promedio, y solo a veces mueve el orden.

Error típico: escribir "el promedio es Θ(n/2), que es mejor que Θ(n)". Θ(n/2) es Θ(n) — la notación asintótica no distingue constantes (01-03). Si quieres comunicar la constante, di "≈ 0,55n comparaciones", no inventes un Θ nuevo.

Dificultad: media

El equipo de RutaBus midió cuatro funciones (F1–F4) con entradas de tamaño creciente y obtuvo estos tiempos (milisegundos):

Y estos son los cuatro códigos, sin decir cuál es cuál:

Empareja A, B, C y D con F1, F2, F3 y F4, razonando a partir de cómo escala el tiempo al duplicar n, y asigna a cada una su Θ.

Pista: al duplicar n, un Θ(n) duplica su tiempo, un Θ(n²) lo cuadruplica, un Θ(log n) suma una cantidad fija minúscula y un Θ(1) no se inmuta. Es la jerarquía de 01-03 vista desde el cronómetro.

Aplicamos la heurística de duplicación:

• F1: 0,8 → 1,6 → 3,2. Se duplica al duplicar n: crecimiento lineal, Θ(n). Es C, que recorre la lista una vez para sumar.
• F2: constante, 0,0004 siempre: Θ(1). Es A: un acceso a matriz por índices no depende de n.
• F3: 90 → 360 → 1 440. Se cuadruplica al duplicar: Θ(n²). Es D, el bucle dependiente de pares (n(n−1)/2 iteraciones, Ejercicio 1).
• F4: 0,0011 → 0,0012 → 0,0013. Suma una cantidad fija diminuta al duplicar n: Θ(log n). Es B: cada vuelta del while reduce el intervalo a la mitad, así que hay ~log₂ n vueltas.

Errores típicos: (1) comparar valores absolutos entre columnas ("F3 es la más lenta, luego es la peor función") — lo que importa es cómo escala, no cuánto vale en un n concreto: para n pequeño un Θ(n²) puede ganar a un Θ(n) con constante grande; (2) confundir Θ(log n) con Θ(1) porque "casi no crece" — crece, y la diferencia importa cuando n tiene nueve cifras.

Dificultad: alta

Esta función genera el informe diario de incidencias de la red. Su autor asegura que "es un solo bucle, así que es O(n)". Tu trabajo: (a) decir cuál es la complejidad real; (b) señalar cada coste oculto con su línea y su coste individual; (c) justificar el total. No hace falta arreglarla (eso es materia de 06-03): solo diagnosticarla con precisión.

(a) La complejidad real es Θ(n²), no Θ(n).

(b) Hay dos costes ocultos, ambos vistos en 02-01:

• Línea A — inc in procesadas: búsqueda lineal sobre una lista que crece. En la iteración i, procesadas tiene hasta i elementos, así que la comprobación cuesta O(i). Sumando: 0 + 1 + … + (n−1) = n(n−1)/2 → Θ(n²) solo esta línea.
• Línea B — informe = informe + ...: las cadenas de Python son inmutables; cada concatenación crea una cadena nueva copiando todo lo anterior. Si el informe llega a tener L caracteres, el coste acumulado de reconstruirlo trocito a trocito es Θ(L²) — y L es proporcional a n, así que también Θ(n²).

(El split(";") de cada línea es O(longitud de la cadena), que tratamos como constante si las incidencias tienen tamaño acotado — este no es un coste oculto problemático.)

(c) Total: Θ(n²) + Θ(n²) = Θ(n²). El "un solo bucle, luego O(n)" falla porque el análisis línea a línea exige el coste de cada operación interna, y aquí dos operaciones de apariencia inocente (un in y un +) esconden recorridos completos de estructuras que crecen con n.

Error típico: detectar uno de los dos costes y dar por terminado el análisis. En código real los costes ocultos vienen en grupo, porque el mismo estilo de programación (acumular sobre lista/cadena y consultar con in) los produce todos a la vez. Acostúmbrate a auditar cada operación del cuerpo del bucle.

Has ejercitado el ciclo completo de análisis del Módulo 2: derivar Θ contando iteraciones (bucles simples, anidados y dependientes con su n(n−1)/2), desenmascarar los costes ocultos de Python (in sobre lista, insert(0), slices que copian, concatenación de cadenas), distinguir espacio auxiliar de total (con la pila de recursión incluida), separar mejor/peor/promedio con distribuciones concretas, y leer órdenes de crecimiento directamente en una tabla de mediciones con la heurística de duplicación.

Si algún ejercicio se te ha resistido, vuelve a la lección correspondiente (02-01 para tiempo y costes ocultos, 02-02 para espacio, 02-03 para casos) y reinténtalo mañana: el análisis de complejidad es de esas habilidades que se consolidan a la segunda pasada. En la siguiente lección cambiamos de músculo: de analizar código dado a diseñar algoritmos nuevos con las cuatro estrategias del Módulo 3.