Algorithmic efficiency · Eficiência algorítmica
What we'll do
- Two programs can both be correct but take very different time.
- This lesson is about efficiency: how the work grows as the input grows.
- Read and think about the ideas; then a few short tasks let you count the steps yourself.
O que faremos
- Dois programas podem estar corretos, mas levar tempos muito diferentes.
- Esta lição trata de eficiência: como o trabalho cresce conforme a entrada cresce.
- Leia e pense nas ideias; então algumas tarefas curtas permitem que você contar os passos sozinho.
Counting the work
- We measure an algorithm by how many steps it does, not seconds.
- Steps in seconds depend on the computer; counting steps does not.
- More input usually means more steps. The question is how much more.
Contando o trabalho
- Medimos um algoritmo pelo quantidade de passos que ele faz, não por segundos.
- Passos em segundos dependem do computador; contar passos não.
- Mais entrada geralmente significa mais passos. A pergunta é quanto mais.
Reasonable vs unreasonable run time
- Some algorithms grow slowly: double the input, do about double the work.
- Some algorithms grow fast: a little more input means a huge jump in work.
- "Reasonable" run time grows slowly enough to finish; "unreasonable" blows up.
Tempo de execução razoável vs irrazoável
- Alguns algoritmos crescem devagar: duplicar a entrada, fazer cerca de dobro do trabalho.
- Alguns algoritmos crescem rápido: um pouco mais de entrada significa um salto enorme no trabalho.
- Tempo de execução "razoável" cresce devagar o suficiente para terminar; "irrazoável" explode.
Input size: 10 20 40
Search a list: 10 20 40 (slow growth - reasonable)
Try all orders: 3,628,800 ... a number with 48 digits (explodes!)
A tiny demo: counting steps
- Below we count the comparisons a linear search makes.
- The count grows in step with the list size — slow, steady growth.
- Try changing the size to see the count follow it.
Uma demonstração pequena: contando passos
- Abaixo contamos as comparações que uma pesquisa linear faz.
- A contagem cresce junto com o tamanho da lista — crescimento lento e constante.
- Tente mudar o tamanho para ver a contância seguir.
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))
When fast is not enough
- Some problems have no known fast algorithm.
- The only methods try a huge number of possibilities — too slow for big input.
- For these, we often accept a good-enough answer instead of the perfect one.
Quando rápido não é suficiente
- Alguns problemas não têm nenhum algoritmo rápido conhecido.
- Os únicos métodos tentam um enorme número de possibilidades — muito lento para entradas grandes.
- Para esses, aceitamos frequentemente uma resposta suficientemente boa em vez da perfeita.
Undecidable problems
- Worse than slow: some problems cannot be solved by any algorithm at all.
- These are called undecidable problems.
- No matter how fast computers get, no program can always give the right answer.
Problemas indecidíveis
- Pior que lento: alguns problemas não podem ser resolvidos por nenhum algoritmo.
- Estes são chamados problemas indecidíveis.
- Não importa quão rápidos os computadores fiquem, nenhum programa pode sempre dar a resposta certa.
Fast : finishes quickly, even for big input
Slow but doable : finishes, but may take a very long time
Undecidable : no algorithm can solve it for every input
Key ideas to remember
- Efficiency is about how work grows with input size.
- Slow-growing algorithms scale to big inputs; fast-growing ones do not.
- Some problems are unreasonable to solve exactly, and some are undecidable.
Ideias principais para lembrar
- Eficiência trata de como o trabalho cresce com o tamanho da entrada.
- Algoritmos de crescimento lento escalam para entradas grandes; os de crescimento rápido não.
- Alguns problemas são irrazoáveis de resolver exatamente, e outros são indecidíveis.
Common mistakes
- Big-O describes how the running time GROWS with the input size.
- A reasonable-time algorithm scales; an unreasonable one does not.
Erros comuns
- Big-O descreve como o tempo de execução CRESCE com o tamanho da entrada.
- Um algoritmo de tempo razoável escala; um irrazoável não.
Now you try
- Write small functions that count steps to feel how the work grows.
- Compare a single loop, a nested loop, and "try all orders". Press Check answer.
Agora você tenta
- Escreva pequenas funções que contam passos para sentir como o trabalho cresce.
- Compare um loop único, um loop aninhado e "tentar todas as ordens". Pressione Check answer.
How algorithms scale · Como os algoritmos escalonam
As input grows, O(n²) explodes while O(log n) barely moves. · À medida que a entrada cresce, O(n²) explode enquanto O(log n) mal se move.
Write scan_compares(data, target) that returns how many comparisons a linear search makes. Compare each item to target, counting one each time, and stop as soon as you find it. If it is not in the list, you compared every item. Example: scan_compares([5, 8, 2], 8) → 2. · Escreva scan_compares(data, target) que retorne quantas comparações uma busca linear faz. Compare cada item a target, contando um a cada vez, e pare assim que encontrá-lo. Se não estiver na lista, você comparou todos os itens. Exemplo: scan_compares([5, 8, 2], 8) → 2.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write pair_count(n) that uses a loop inside a loop (both over range(n)) and returns how many times the inner step runs. This is n × n. Example: pair_count(3) → 9. This grows much faster than a single loop. · Escreva pair_count(n) que use um loop dentro de outro loop (ambos sobre range(n)) e retorne quantas vezes o passo interno roda. Este é n × n. Exemplo: pair_count(3) → 9. Este cresce muito mais rápido que um único loop.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write count_orderings(n) that returns how many different orders n items can be placed in — that is 1 × 2 × ... × n (n factorial). count_orderings(0) is 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million. · Escreva count_orderings(n) que retorne quantas ordens diferentes n itens podem ser colocados — isso é 1 × 2 × ... × n (fatorial de n). count_orderings(0) é 1. Exemplo: count_orderings(3) → 6. Note como explode rápido: count_orderings(10) é mais de 3 milhões.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.