Algorithmic Efficiency
Introduzido| English | Significado |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | eficiência algorítmica |
| slow/sləʊ/ | lento |
| steps/steps/ | etapas |
| reasonable/ˈriːzənəbl/ | razoável |
| unreasonable/ʌnˈriːzənəbl/ | irracional |
| heuristic/hjuːˈrɪstɪk/ | heurística |
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 consomem — 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:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Efficiency is about time and memory as input grows.
Contando passos conforme n cresce
- Estime o número de passos que um algoritmo executa conforme seu tamanho de entrada $n$ cresce.
- 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.

Como o tempo de execução de um algoritmo cresce com o tamanho da 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.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
These growth rates decide which algorithm scales.
Which growth is considered unreasonable as n gets large?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Exponential growth quickly becomes far too slow.
When an exact answer is too slow, a ______ finds a good-enough solution fast.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
A heuristic trades a perfect answer for speed.
Razoável vs irrazoável
- Separamos um tempo de execução razoável de um irracional.
- Aproximadamente, crescimento como $n$ ou $n^2$ é razoável; dobrar os passos por item extra (como $2^n$) não é.
- Quando uma resposta exata é muito lenta, use uma heurística — uma solução aceitável 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)
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
False. A correct algorithm can still be too slow on large inputs; it must also finish in a reasonable time.
Muito lento para usar
- É por isso que alguns algoritmos corretos são demasiado lentos para serem executados na prática com grandes entradas.
- 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.
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.