Algoritmos Avanzados en Python

1. Para detectar ids repetidos en 2000 pedidos, un doble ciclo hace 1,999,000 comparaciones y la versión con set hace 2000 operaciones. Si los pedidos se duplican a 4000, ¿qué se espera de cada versión?

• Ambas versiones harán el doble de trabajo
• El doble ciclo hará el doble y la versión con set, 4 veces más
• El doble ciclo hará unas 4 veces más comparaciones y la versión con set, unas 2 veces más operaciones
• Ninguna cambia, porque la complejidad no depende del tamaño de la entrada

El doble ciclo compara cada par, n(n−1)/2, y es O(n²): al duplicar n el trabajo se multiplica por cerca de 4. La versión con set es O(n) en promedio: el trabajo se duplica.

2. Un programador reemplaza el set vistos por una lista en la detección de repetidos: «if x in vistos: ...; vistos.append(x)». ¿Qué pasa con la complejidad?

• Vuelve a ser O(n²), porque cada «x in lista» es O(n) y se hace dentro del ciclo
• Sigue siendo O(n), porque solo hay un ciclo for
• Mejora a O(log n), porque append es O(1) amortizado
• Sigue siendo O(n) en tiempo, pero usa O(n²) memoria

x in lista recorre la lista: O(n). Dentro de un ciclo de n elementos, el algoritmo vuelve a O(n²) aunque el código tenga un solo for. En un set o dict, in cuesta O(1) en promedio.

3. La búsqueda lineal en 100,000 SKUs hace 1 comparación en el mejor caso, 100,000 en el peor y unas 50,526 de media. ¿Cómo se clasifica su caso promedio?

• Θ(log n), porque en promedio se recorre solo la mitad
• Θ(1), porque el mejor caso es una comparación
• Θ(n²), porque se buscan 1000 SKUs distintos
• Θ(n): la mitad de n sigue creciendo de forma lineal

Big O ignora las constantes: 50,526 es cerca de n/2, y n/2 sigue creciendo linealmente con n. El caso promedio y el peor caso son Θ(n).

4. fib(30) ingenuo hace 2,692,537 llamadas; con @lru_cache se calculan solo 31 valores distintos. ¿De dónde sale el ahorro?

• lru_cache ejecuta las llamadas en paralelo
• Los subproblemas se repiten; la caché guarda cada fib(k) la primera vez y luego lo reutiliza
• lru_cache aumenta el límite de recursión de Python
• La versión con caché usa una fórmula cerrada en lugar de recursión

El árbol de llamadas de fib repite los mismos subproblemas una y otra vez. La memoización guarda cada resultado la primera vez y lo reutiliza: solo hay 31 subproblemas distintos (fib(0) a fib(30)).

5. Para la camioneta de 50 kg, elegir paquetes por mayor valor/peso da 10,231 MXN, mientras la programación dinámica da 10,581 MXN con 770 estados. ¿Qué muestra esta comparación?

• La programación dinámica es una heurística que a veces supera al voraz por suerte
• El voraz falla porque ordena mal; ordenando por peso daría siempre el óptimo
• El voraz es rápido pero no garantiza el óptimo en la mochila 0/1; la programación dinámica sí, reutilizando estados
• Ambos métodos son exactos; la diferencia se debe a errores de redondeo

En la mochila 0/1 los paquetes no se pueden partir, así que la estrategia voraz puede dejar capacidad mal aprovechada (46 kg usados). La programación dinámica explora los estados (paquete, capacidad restante) y garantiza el óptimo.