Algorithmic efficiency · Eficiencia algorítmica
Qué haremos
- Dos programas pueden ser ambos correctos pero requerir tiempos muy diferentes.
- Esta lección trata sobre la eficiencia: cómo crece el trabajo a medida que crece la entrada.
- Lee y reflexiona sobre las ideas; luego, unas pocas tareas cortas te permitirán contar los pasos tú mismo.
Contando el trabajo
- Medimos un algoritmo por cuántos pasos ejecuta, no por segundos.
- Los pasos en segundos dependen de la computadora; contar pasos no.
- Más entrada suele significar más pasos. La pregunta es cuánto más.
Tiempo de ejecución razonable vs. irrazonable
- Algunos algoritmos crecen lentamente: duplicar la entrada implica hacer aproximadamente el doble de trabajo.
- Algunos algoritmos crecen rápidamente: un poco más de entrada significa un salto enorme en el trabajo.
- Un tiempo de ejecución "razonable" crece lo suficientemente lento como para terminar; uno "irrazonable" se dispara descontroladamente.
Input size: 10 20 40
Search a list: 10 20 40 (slow growth - reasonable)
Try all orders: 3,628,800 ... a number with 48 digits (explodes!)
Una pequeña demostración: contando pasos
- A continuación contamos las comparaciones que hace una búsqueda lineal.
- El conteo crece al ritmo del tamaño de la lista — crecimiento lento y constante.
- Prueba cambiar el tamaño para ver cómo el conteo lo sigue.
def count_steps(n):
steps = 0
data = list(range(n))
target = -1 # not in the list, so we scan everything
for item in data:
steps = steps + 1
if item == target:
break
return steps
print(count_steps(10))
print(count_steps(20))
print(count_steps(40))
Cuando lo rápido no es suficiente
- Algunos problemas no tienen ningún algoritmo rápido conocido.
- Los únicos métodos prueban un enorme número de posibilidades — demasiado lentos para entradas grandes.
- Para estos, a menudo aceptamos una respuesta suficientemente buena en lugar de la perfecta.
Problemas indecidibles
- Peor que lento: algunos problemas no pueden ser resueltos por ningún algoritmo en absoluto.
- Estos se llaman problemas indecidibles.
- No importa qué tan rápidas sean las computadoras, ningún programa puede dar siempre la respuesta correcta.
Fast : finishes quickly, even for big input
Slow but doable : finishes, but may take a very long time
Undecidable : no algorithm can solve it for every input
Ideas clave para recordar
- La eficiencia trata sobre cómo crece el trabajo con el tamaño de la entrada.
- Los algoritmos de crecimiento lento escalan bien a entradas grandes; los de crecimiento rápido no.
- Algunos problemas son irrazonables de resolver exactamente, y otros son indecidibles.
Errores comunes
- Big-O describe cómo crece el tiempo de ejecución con el tamaño de la entrada.
- Un algoritmo de tiempo razonable escala; uno irrazonable no.
Ahora te toca a ti
- Escribe funciones pequeñas que cuenten pasos para sentir cómo crece el trabajo.
- Compara un bucle simple, un bucle anidado y "probar todos los órdenes". Presiona Comprobar respuesta.
How algorithms scale · Cómo escalan los algoritmos
As input grows, O(n²) explodes while O(log n) barely moves. · A medida que crece la entrada, O(n²) explota mientras que O(log n) apenas se mueve.
Write scan_compares(data, target) that returns how many comparisons a linear search makes. Compare each item to target, counting one each time, and stop as soon as you find it. If it is not in the list, you compared every item. Example: scan_compares([5, 8, 2], 8) → 2. · Escribe scan_compares(data, target) que devuelva cuántas comparaciones realiza una búsqueda lineal. Compara cada elemento con target, contando uno cada vez, y detente tan pronto como lo encuentres. Si no está en la lista, comparaste todos los elementos. Ejemplo: scan_compares([5, 8, 2], 8) → 2.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write pair_count(n) that uses a loop inside a loop (both over range(n)) and returns how many times the inner step runs. This is n × n. Example: pair_count(3) → 9. This grows much faster than a single loop. · Escribe pair_count(n) que use un bucle dentro de otro bucle (ambos sobre range(n)) y devuelva cuántas veces se ejecuta el paso interno. Esto es n × n. Ejemplo: pair_count(3) → 9. Esto crece mucho más rápido que un solo bucle.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write count_orderings(n) that returns how many different orders n items can be placed in — that is 1 × 2 × ... × n (n factorial). count_orderings(0) is 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million. · Escribe count_orderings(n) que devuelva cuántos órdenes diferentes pueden tener n elementos — es decir, 1 × 2 × ... × n (factorial de n). count_orderings(0) es 1. Ejemplo: count_orderings(3) → 6. Nota qué tan rápido explota: count_orderings(10) supera los 3 millones.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.