Algorithmic Efficiency
Introducido| English | Significado |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | eficiencia algorítmica |
| slow/sləʊ/ | lento |
| steps/steps/ | pasos |
| reasonable/ˈriːzənəbl/ | razonable |
| unreasonable/ʌnˈriːzənəbl/ | irrazonable |
| heuristic/hjuːˈrɪstɪk/ | heurística |
Correcto no siempre es suficiente
- Dos algoritmos pueden ser ambos correctos, pero uno puede ser mucho mejor de usar.
- Eficiencia algorítmica compara algoritmos según los recursos que utilizan, principalmente tiempo y memoria.
- Un algoritmo correcto pero lento puede ser inútil para entradas grandes.
- Por lo tanto, necesitamos una forma de comparar cómo escalan.
Algorithmic efficiency compares algorithms by:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Efficiency is about time and memory as input grows.
Contando pasos a medida que n crece
- Estimar el número de pasos que un algoritmo requiere a medida que su tamaño de entrada $n$ crece.
- Una búsqueda lineal toma aproximadamente $n$ pasos; una búsqueda binaria alrededor de $\log_2 n$; comparar cada par tomará unos $n^2$.
- A medida que $n$ se hace grande, estas diferencias se vuelven inmensas.
- La forma del crecimiento importa mucho más que un cronómetro.

Cómo crece el tiempo de ejecución de un algoritmo con el tamaño de entrada n
How running time grows with n
Slide n and compare the curves: log n stays almost flat, n rises steadily, n² explodes. This is why we compare algorithms by how they scale, not with a stopwatch.
Match each algorithm to its rough number of steps for input size n.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
These growth rates decide which algorithm scales.
Which growth is considered unreasonable as n gets large?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Exponential growth quickly becomes far too slow.
When an exact answer is too slow, a ______ finds a good-enough solution fast.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
A heuristic trades a perfect answer for speed.
Razonable vs irrazonable
- Diferenciar entre un tiempo de ejecución razonable y uno irrazonable.
- Aproximadamente, un crecimiento como $n$ o $n^2$ es razonable; duplicar los pasos por elemento adicional (como $2^n$) no lo es.
- Cuando una respuesta exacta es demasiado lenta, usar una heurística: una solución aceptable encontrada rápidamente.
- No es perfecta, pero es útil cuando lo perfecto es imposible en tiempo.
A binary search of 1,000,000 sorted items needs at most about how many steps? (2^20 ≈ a million)
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Because 2^20 is just over a million, ~20 halvings suffice.
If an algorithm is correct, it will always run fast enough on large inputs.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
False. A correct algorithm can still be too slow on large inputs; it must also finish in a reasonable time.
Demasiado lento para usar
- Por eso algunos algoritmos correctos son demasiado lentos para ejecutarse en la práctica con entradas grandes.
- Ser correcto no es suficiente: un algoritmo también debe terminar en un tiempo razonable.
Un millón de elementos. Una búsqueda lineal de 1,000,000 elementos ordenados puede tomar hasta 1,000,000 pasos. Una búsqueda binaria toma como máximo unos 20, porque $2^{20}$ está apenas sobre un millón. En listas pequeñas la diferencia apenas importa; con un millón de elementos, la binaria es la única opción razonable.
La eficiencia algorítmica compara algoritmos por recursos a medida que el tamaño de entrada $n$ crece: lineal $n$, binario $\log_2 n$, todos los pares $n^2$. Un crecimiento como $n$ o $n^2$ es razonable; $2^n$ es irrazonable (use un heurístico). Un algoritmo correcto que es demasiado lento en entradas grandes no es suficiente.