Algorithmic Efficiency · Eficiencia Algorítmica
| English | Español |
|---|---|
| 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 |
Correct isn't always good enough
- Two algorithms can both be correct, yet one may be far better to use.
- Algorithmic efficiency 算法效率 compares algorithms by the resources they use — mainly time and memory.
- A correct-but-slow algorithm can be useless on large inputs.
- So we need a way to compare how they scale.
Correcto no siempre es suficiente
- Dos algoritmos pueden ser ambos correctos, pero uno puede ser mucho mejor de usar.
- La eficiencia algorítmica 算法效率 compara algoritmos por 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: · La eficiencia algorítmica compara algoritmos según:
Efficiency is about time and memory as input grows. · La eficiencia se refiere al tiempo y la memoria a medida que crece la entrada.
Counting steps as n grows
- Estimate the number of steps 步骤 an algorithm takes as its input size $n$ grows.
- A linear search takes about $n$ steps; a binary search about $\log_2 n$; comparing every pair about $n^2$.
- As $n$ gets large, these differences become huge.
- The shape of the growth matters far more than a stopwatch.
Contando pasos a medida que n crece
- Estimar el número de pasos 步骤 que toma un algoritmo 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.
How running time grows with n · Cómo crece el tiempo de ejecución con 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. · Desliza n y compara las curvas: log n se mantiene casi plano, n aumenta de forma constante, n² explota. Por eso comparamos algoritmos por su escalabilidad, no con un cronómetro.
Match each algorithm to its rough number of steps for input size n. · Asocia cada algoritmo con su número aproximado de pasos para un tamaño de entrada n.
These growth rates decide which algorithm scales. · Estas tasas de crecimiento determinan qué algoritmo escala mejor.
Which growth is considered unreasonable as n gets large? · ¿Cuál de los siguientes crecimientos se considera irrazonable cuando n es grande?
Exponential growth quickly becomes far too slow. · El crecimiento exponencial rápidamente se vuelve demasiado lento.
When an exact answer is too slow, a ______ finds a good-enough solution fast. · Cuando una respuesta exacta es demasiado lenta, una ______ encuentra una solución suficientemente buena rápidamente.
A heuristic trades a perfect answer for speed. · Una heurística intercambia una respuesta perfecta por velocidad.
Reasonable vs unreasonable
- We separate a reasonable 合理 running time from an unreasonable 不合理 one.
- Roughly, growth like $n$ or $n^2$ is reasonable; doubling steps per extra item (like $2^n$) is not.
- When an exact answer is too slow, use a heuristic 启发式方法 — a good-enough solution found fast.
- Not perfect, but useful when perfect is impossible in time.
Razonable vs irrazonable
- Separamos un tiempo de ejecución razonable 合理 de 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, use un heurístico 启发式方法 —una solución buena y suficiente 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) · Una búsqueda binaria en 1,000,000 elementos ordenados necesita como máximo unos cuántos pasos? (2^20 ≈ un millón)
Because 2^20 is just over a million, ~20 halvings suffice. · Como 2^20 es apenas superior a un millón, ~20 divisiones por la mitad son suficientes.
A correct algorithm can still be too slow to use on large inputs. · Un algoritmo correcto puede seguir siendo demasiado lento para usarse con entradas grandes.
It must also finish in a reasonable time. · También debe terminar en un tiempo razonable.
Too slow to use
- This is why some correct algorithms are too slow 缓慢 to run in practice on large inputs.
- Being correct is not enough — an algorithm must also finish in a reasonable time.
A million items. A linear search of 1,000,000 sorted items may take up to 1,000,000 steps. A binary search takes at most about 20, because $2^{20}$ is just over a million. On small lists the gap barely matters; on a million items, binary is the only reasonable choice.
Demasiado lento para usar
- Es por esto que 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.
Algorithmic efficiency compares algorithms by resources as input size $n$ grows: linear $n$, binary $\log_2 n$, all-pairs $n^2$. Growth like $n$ or $n^2$ is reasonable; $2^n$ is unreasonable (use a heuristic). A correct algorithm that is too slow on large inputs is not good enough.
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.