Análise Informal de Tempo de Execução
Introduzido| English | Significado |
|---|---|
| run time/rʌn taɪm/ | tempo de execução |
| linear/ˈlɪnɪə/ | linear |
| quadratic/kwɒˈdrætɪk/ | quadrática |
Um único loop: cerca de n
- Medimos o tempo de execução de um programa pelo número de vezes que suas instruções principais são executadas.
- Não segundos (que variam conforme a máquina) — uma contagem de operações à medida que a entrada cresce.
- Mais operações para o mesmo tamanho de entrada → algoritmo mais lento.
- Isso nos permite comparar algoritmos justos, independentemente do hardware.
Um único loop: sobre n
- Um loop sobre
nitens executa seu corpo aproximadamentenvezes. - Dobrar a entrada → aproximadamente dobrar o trabalho. Este é crescimento linear.
- Escrito informalmente como "ordem
n." - Escrito informalmente como "ordem
n."

Como o tempo de execução cresce com o número de elementos n
Um loop aninhado: sobre n²
- Comparar todos os pares, preencher uma grade
n: cerca den × n = n²passos. - Dobrar a entrada → aproximadamente quatro vezes o trabalho. Este é crescimento quadrático.
- Comparando todos os pares, preenchendo uma matriz
n × n: cerca den²etapas. n²cresce muito mais rápido quenà medida quense torna grande.
Comparando crescimentos
- Para comparar algoritmos, pergunte como o trabalho cresce à medida que a entrada cresce.
- Para grandes
n, um algoritmonsupera um algoritmon²— frequentemente em muito. - Foque na parte do código que executa mais (geralmente o loop mais interno).
- O termo que mais cresce domina o tempo de execução total.
Avalie a complexidade temporal pelo crescimento, não por um valor fixo. Um algoritmo que executa n etapas e outro que executa 2n + 5 etapas crescem linearmente — para fins de comparação, a constante e o +5 não importam; o formato (n versus n²) é o que importa. Um único loop está relacionado ao n; um loop aninhado está relacionado ao n², que cresce muito mais rápido para entradas grandes.
Duas maneiras de encontrar duplicatas em n itens:
- Loops aninhados comparando cada par: cerca de
n²etapas. - Ordenar primeiro, depois uma única passagem: muito menos etapas para grandes
n. - Para
n = 1000,n²é um milhão de etapas — a abordagem don²é muito mais lenta.
A análise informal do tempo de execução conta quantas vezes as instruções são executadas à medida que a entrada cresce. Um loop único sobre n itens é cerca de n (linear); um loop aninhado é cerca de n² (quadrático), o que cresce muito mais rápido. Compare algoritmos por seu crescimento, focando no código mais executado (mais interno).
Como o trabalho cresce com n
Um laço aninhado (n²) cresce muito mais rápido do que um laço único (n).
Um laço único sobre n itens roda seu corpo aproximadamente quantas vezes?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Um laço sobre n itens → cerca de n passos (linear).
Um laço aninhado sobre n itens roda seu corpo interno aproximadamente quantas vezes?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
n × n = n² (quadrático).
Para n = 1000, aproximadamente quantos passos tem um algoritmo n² (em milhões)?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
1000² = 1,000,000 = 1 milhão.
Para n grande, um algoritmo de n passos é geralmente mais rápido do que um de n² passos.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
n² cresce muito mais rápido, então executa muito mais trabalho em n grandes.
Medimos o tempo de execução em segundos, que é igual em todos os computadores.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Contamos operações vs. tamanho de entrada — segundos variam pela máquina.