Informal Run-Time Analysis · Análise Informal de Tempo de Execução
| English | Português |
|---|---|
| run time/rʌn taɪm/ | tempo de execução |
| linear/ˈlɪnɪə/ | linear |
| quadratic/kwɒˈdrætɪk/ | quadrática |
Counting the work
- We measure a program's run time 运行时间 by how many times its key statements run.
- Not seconds (those vary by machine) — a count of operations as the input grows.
- More operations for the same input size → slower algorithm.
- This lets us compare algorithms fairly, independent of hardware.
Um único loop: cerca de n
- Medimos o tempo de execução 运行时间 de um programa pela quantidade de vezes que suas principais instruções 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.
A single loop: about n
- A loop over
nitems runs its body aboutntimes. - Double the input → about double the work. This is linear 线性 growth.
- Summing an array, searching a list one-by-one: all about
nsteps. - Written informally as "order
n."
Um único loop: sobre n
- Um loop sobre
nitens executa seu corpo aproximadamentenvezes. - Dobrar a entrada → cerca do dobro do trabalho. Isso é crescimento linear 线性增长.
- Escrito informalmente como "ordem
n." - Escrito informalmente como "ordem
n."
A nested loop: about n²
- A nested loop over
nitems runs its inner body aboutn × n = n²times. - Double the input → about four times the work. This is quadratic 二次 growth.
- Comparing all pairs, filling an
n × ngrid: aboutn²steps. n²grows much faster thannasngets large.
Um loop aninhado: sobre n²
- Comparar todos os pares, preencher uma grade
n: cerca den × n = n²passos. - Dobrar a entrada → cerca de quatro vezes o trabalho. Isso é 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.
Comparing growth
- To compare algorithms, ask how the work grows as the input grows.
- For large
n, annalgorithm beats ann²algorithm — often by a lot. - Focus on the part of the code that runs the most (usually the innermost loop).
- The fastest-growing term dominates the total run time.
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.
Judge run time by GROWTH, not a fixed count. An algorithm that does n steps and one that does 2n + 5 steps both grow linearly — for comparing, the constant and the +5 don't matter; the shape (n vs n²) does. A single loop is about n; a nested loop is about n², which grows far faster for large inputs.
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.
Two ways to find duplicates in n items:
- Nested loops comparing every pair: about
n²steps. - Sort first, then one pass: far fewer steps for large
n. - For
n = 1000,n²is a million steps — then²approach is much slower.
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.
Informal run-time analysis counts how many times statements run as the input grows. A single loop over n items is about n (linear); a nested loop is about n² (quadratic), which grows much faster. Compare algorithms by their growth, focusing on the most-executed (innermost) code.
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).
How the work grows with n · Como o trabalho cresce com n
A nested loop (n²) grows far faster than a single loop (n). · Um laço aninhado (n²) cresce muito mais rápido do que um laço único (n).
A single loop over n items runs its body about how many times? · Um laço único sobre n itens roda seu corpo aproximadamente quantas vezes?
One loop over n items → about n steps (linear). · Um laço sobre n itens → cerca de n passos (linear).
A nested loop over n items runs its inner body about how many times? · Um laço aninhado sobre n itens roda seu corpo interno aproximadamente quantas vezes?
n × n = n² (quadratic). · n × n = n² (quadrático).
For n = 1000, about how many steps is an n² algorithm (in millions)? · Para n = 1000, aproximadamente quantos passos tem um algoritmo n² (em milhões)?
1000² = 1,000,000 = 1 million. · 1000² = 1,000,000 = 1 milhão.
For large n, an n-step algorithm is generally faster than an n²-step one. · Para n grande, um algoritmo de n passos é geralmente mais rápido do que um de n² passos.
n² grows much faster, so it does far more work at large n. · n² cresce muito mais rápido, então executa muito mais trabalho em n grandes.
We measure run time in seconds, which is the same on every computer. · Medimos o tempo de execução em segundos, que é igual em todos os computadores.
We count operations vs. input size — seconds vary by machine. · Contamos operações vs. tamanho de entrada — segundos variam pela máquina.