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 breves te permiten contar los pasos por ti mismo.
Contando el trabajo
- Medimos un algoritmo por cuántos pasos ejecuta, no en 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
- Un tiempo razonable significa que el número de pasos crece como un polinomio, o más lentamente: constante, lineal, cuadrático o cúbico.
- Un bucle simple es lineal. Un bucle dentro de otro es cuadrático (n × n). Lo cuadrático crece más rápido que lo lineal, y aún es un tiempo razonable.
- Un tiempo irrazonable implica crecimiento exponencial o factorial. Un poco más de entrada hace que el trabajo se dispare.
Input size: 10 20 40
Search a list: 10 20 40 (linear - reasonable)
Nested loops: 100 400 1,600 (square - still reasonable)
Try all orders: 3,628,800 ... 48 digits (factorial - unreasonable)
Una demostración breve: contando pasos
- A continuación, contamos las comparaciones que realiza una búsqueda lineal.
- El conteo aumenta al ritmo de la tamaño de la lista: un 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 la velocidad no basta
- Algunos problemas no tienen ningún algoritmo conocido de tiempo razonable.
- Un método exacto puede intentar cada orden. Esto es crecimiento factorial, por lo que es irrazonable para una entrada grande.
- Una heurística es un atajo que puede dar una respuesta suficientemente buena. No está garantizado que sea la mejor. No necesitas memorizar una heurística en particular.
Problemas indecidibles
- Peor que lento: algunos problemas no pueden ser resueltos por ningún algoritmo.
- Estos se denominan problemas indécidos.
- Independientemente de la velocidad de los computadores, ningún programa puede dar siempre la respuesta correcta.
Reasonable : constant, linear, square or cube growth
Unreasonable : exponential or factorial growth
Undecidable : no algorithm can solve it for every input
Ideas clave para recordar
- La eficiencia se refiere a cómo crece el número de pasos con el tamaño de la entrada, no a cuántos segundos tarda un computador en ejecutarse.
- Un crecimiento polinomial o inferior es razonable. Un bucle anidado (n × n) sigue siendo razonable.
- Un crecimiento exponencial o factorial es irrazonable. Algunos problemas también son indecibles.
Errores comunes
- Llamar irrazonable a un bucle anidado es incorrecto. El crecimiento cuadrático y cúbico sigue siendo razonable.
- Utilizar la notación formal Big-O como regla de examen. No se evalúa Big-O. La línea divisoria es entre polinomial o inferior, frente a exponencial o factorial.
Ahora tú prueban
- Escribir funciones pequeñas que cuenten pasos para percibir cómo crece el trabajo.
- Comparar un bucle simple, un bucle anidado y "probar todos los órdenes". El bucle anidado sigue siendo razonable. Presiona Verificar respuesta.
Cómo escalan los algoritmos
El crecimiento cuadrático aumenta más rápido que una línea recta, y sigue siendo razonable en tiempo. El crecimiento factorial es irrazonable.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
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.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
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.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
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.
Haz clic en Ejecutar para ver la salida aquí.