Algorithmic efficiency
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.
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.
Tempo de execução razoável vs irrazoável
- Tempo razoável significa que o número de passos cresce como um polinômio, ou mais lentamente: constante, linear, quadrático ou cúbico.
- Um único laço é linear. Um laço dentro de outro é quadrático (n × n). O crescimento quadrático é mais rápido que o linear, mas ainda representa tempo razoável.
- Tempo irrazoável significa crescimento exponencial ou fatorial. Um pequeno aumento na entrada faz o trabalho explodir.
Input size: 10 20 40
Search a list: 10 20 40 (linear - reasonable)
Nested loops: 100 400 1,600 (square - still reasonable)
Try all orders: 3,628,800 ... 48 digits (factorial - unreasonable)
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))
Quando rápido não é suficiente
- Alguns problemas não possuem algoritmo conhecido com tempo razoável.
- Um método exato pode tentar todas as permutações. Isso é crescimento fatorial, sendo irrazoável para uma grande entrada.
- Uma heurística é um atalho que pode fornecer uma resposta aceitável. Não há garantia de que seja a melhor. Você não precisa memorizar uma heurística específica.
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.
Reasonable : constant, linear, square or cube growth
Unreasonable : exponential or factorial growth
Undecidable : no algorithm can solve it for every input
Ideias principais para lembrar
- Eficiência refere-se a como o número de passos cresce com o tamanho da entrada, e não aos segundos que um computador leva.
- Crescimento polinomial ou inferior é tempo razoável. Um laço aninhado (n × n) ainda é considerado razoável.
- Crescimento exponencial ou fatorial é irrazoável. Alguns problemas também são indecidíveis.
Erros comuns
- Chamar um laço aninhado de irrazoável está incorreto. Crescimento quadrático e cúbico ainda representam tempo razoável.
- Usar notação Big-O formal como regra de prova. A notação Big-O não é cobrada em provas. A linha deve ser polinomial ou inferior, versus exponencial ou fatorial.
Agora você tenta
- Escreva pequenas funções que contam passos para sentir como o trabalho cresce.
- Compare um único laço, um laço aninhado e "tentar todas as ordens". O laço aninhado ainda tem tempo razoável. Pressione Verificar resposta.
How algorithms scale
Square growth rises faster than a straight line, and it is still reasonable time. Factorial growth is unreasonable.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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) é 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million.
Clique em Executar para ver a saída aqui.