Algorithmic Efficiency · Eficiência Algorítmica
| English | Português |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | Eficiência algorítmica |
| slow/sləʊ/ | lenta |
| steps/steps/ | passos |
| reasonable/ˈriːzənəbl/ | razoável |
| unreasonable/ʌnˈriːzənəbl/ | irracional |
| 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.
Correto nem sempre é suficiente
- Dois algoritmos podem ambos estar corretos, mas um pode ser muito melhor de usar.
- Eficiência algorítmica 算法效率 compara algoritmos pelos recursos que usam — principalmente tempo e memória.
- Um algoritmo correto, mas lento, pode ser inútil em grandes entradas.
- Então precisamos de uma maneira de comparar como eles escalam.
Algorithmic efficiency compares algorithms by: · A eficiência algorítmica compara algoritmos por:
Efficiency is about time and memory as input grows. · A eficiência trata-se de tempo e memória conforme a entrada cresce.
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 passos conforme n cresce
- Estime o número de passos 步骤 que um algoritmo leva conforme o tamanho de sua entrada $n$ aumenta.
- Uma busca linear leva cerca de $n$ passos; uma busca binária cerca de $\log_2 n$; comparar todos os pares cerca de $n^2$.
- Conforme $n$ fica grande, essas diferenças tornam-se enormes.
- A forma do crescimento importa muito mais do que um cronômetro.
How running time grows with n · Como o tempo de execução cresce com 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. · Deslize n e compare as curvas: log n permanece quase plano, n sobe consistentemente, n² explode. É por isso que comparamos algoritmos pela forma como escalam, não com um cronômetro.
Match each algorithm to its rough number of steps for input size n. · Corresponda cada algoritmo ao seu número aproximado de passos para tamanho de entrada n.
These growth rates decide which algorithm scales. · Essas taxas de crescimento decidem qual algoritmo escala melhor.
Which growth is considered unreasonable as n gets large? · Qual crescimento é considerado irracional quando n fica grande?
Exponential growth quickly becomes far too slow. · O crescimento exponencial rapidamente se torna muito lento demais.
When an exact answer is too slow, a ______ finds a good-enough solution fast. · Quando uma resposta exata é muito lenta, um ______ encontra uma solução boa o suficiente rapidamente.
A heuristic trades a perfect answer for speed. · Uma heurística troca uma resposta perfeita por velocidade.
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.
Razoável vs irrazoável
- Separamos um tempo de execução razoável 合理 de um irrazoável 不合理.
- Aproximadamente, crescimento como $n$ ou $n^2$ é razoável; dobrar os passos por item extra (como $2^n$) não é.
- Quando uma resposta exata for muito lenta, use um heurístico 启发式方法 — uma solução boa o suficiente encontrada rapidamente.
- Não perfeita, mas útil quando a solução perfeita é impossível dentro do tempo disponível.
A binary search of 1,000,000 sorted items needs at most about how many steps? (2^20 ≈ a million) · Uma busca binária de 1,000,000 itens ordenados precisa de, no máximo, aproximadamente quantos passos? (2^20 ≈ um milhão)
Because 2^20 is just over a million, ~20 halvings suffice. · Porque 2^20 é pouco mais de um milhão, ~20 divisões por dois bastam.
A correct algorithm can still be too slow to use on large inputs. · Um algoritmo correto ainda pode ser muito lento para usar em entradas grandes.
It must also finish in a reasonable time. · Ele também deve terminar em um tempo razoável.
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.
Muito lento para usar
- É por isso que alguns algoritmos corretos são muito lentos 缓慢 para serem executados na prática com entradas grandes.
- Ser correto não basta — um algoritmo também deve terminar em um tempo razoável.
Um milhão de itens. Uma busca linear em 1,000,000 itens ordenados pode levar até 1,000,000 etapas. Uma busca binária leva no máximo cerca de 20, porque $2^{20}$ é pouco mais de um milhão. Em listas pequenas, a diferença é quase irrelevante; em um milhão de itens, a busca binária é a única escolha razoável.
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.
Eficiência algorítmica compara algoritmos por recursos à medida que o tamanho da entrada $n$ cresce: linear $n$, binária $\log_2 n$, todos os pares $n^2$. Crescimento como $n$ ou $n^2$ é razoável; $2^n$ é irracional (use um heurístico). Um algoritmo correto que seja muito lento em entradas grandes não é bom o suficiente.