Informal Run-Time Analysis · Analyse informelle du temps d'exécution
| English | Français |
|---|---|
| run time/rʌn taɪm/ | temps d'exécution |
| linear/ˈlɪnɪə/ | linéaire |
| quadratic/kwɒˈdrætɪk/ | quadratique |
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.
Compter le travail
- Nous mesurons le temps d'exécution 运行时间 d'un programme par le nombre de fois que ses instructions clés s'exécutent.
- Pas en secondes (celles-ci varient selon la machine) — un comptage d'opérations à mesure que l'entrée augmente.
- Plus d'opérations pour la même taille d'entrée → algorithme plus lent.
- Cela permet de comparer les algorithmes équitablement, indépendamment du matériel.
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."
Une seule boucle : environ n
- Une boucle sur
néléments exécute son corps environnfois. - Doubler l'entrée → environ double le travail. C'est une croissance linéaire 线性.
- Sommer un tableau, chercher dans une liste un par un : tout est environ
nétapes. - Écrit informellement comme « ordre
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.
Une boucle imbriquée : environ n²
- Une boucle imbriquée sur
néléments exécute son corps intérieur environn × n = n²fois. - Doubler l'entrée → environ quatre fois le travail. C'est une croissance quadratique 二次.
- Comparer toutes les paires, remplir une grille
n × n: environn²étapes. n²croît beaucoup plus vite quenlorsquendevient grand.
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.
Comparer la croissance
- Pour comparer des algorithmes, demandez-vous comment le travail croît à mesure que l'entrée augmente.
- Pour une grande
n, un algorithmenbat un algorithmen²— souvent de beaucoup. - Concentrez-vous sur la partie du code qui s'exécute le plus (généralement la boucle la plus interne).
- Le terme croissant le plus domine le temps d'exécution 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.
Jugez le temps d'exécution par la CROISSANCE, pas par un comptage fixe. Un algorithme qui fait n étapes et un qui en fait 2n + 5 croissent tous deux linéairement — pour comparer, la constante et le +5 n'ont pas d'importance ; c'est la forme (n vs n²) qui l'emporte. Une boucle simple est environ n ; une boucle imbriquée est environ n², ce qui croît beaucoup plus vite pour les grandes entrées.
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.
Deux façons de trouver des doublons dans n éléments :
- Boucles imbriquées comparant chaque paire : environ
n²étapes. - Trier d'abord, puis un seul passage : bien moins d'étapes pour de grandes
n. - Pour
n = 1000,n²représente un million d'étapes — l'approchen²est beaucoup plus lente.
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.
L'analyse informelle du temps d'exécution compte combien de fois les instructions s'exécutent à mesure que l'entrée augmente. Une boucle simple sur n éléments est environ n (linéaire) ; une boucle imbriquée est environ n² (quadratique), ce qui croît beaucoup plus vite. Comparez les algorithmes par leur croissance, en vous concentrant sur le code le plus exécuté (le plus interne).
How the work grows with n · Comment le travail augmente avec n
A nested loop (n²) grows far faster than a single loop (n). · Une boucle imbriquée (n²) croît beaucoup plus vite qu'une boucle unique (n).
A single loop over n items runs its body about how many times? · Une boucle unique sur n éléments s'exécute environ combien de fois ?
One loop over n items → about n steps (linear). · Une boucle sur n éléments → environ n étapes (linéaire).
A nested loop over n items runs its inner body about how many times? · Une boucle imbriquée sur n éléments s'exécute environ combien de fois son corps interne ?
n × n = n² (quadratic). · n × n = n² (quadratique).
For n = 1000, about how many steps is an n² algorithm (in millions)? · Pour n = 1000, environ combien d'étapes représente un algorithme n² (en millions) ?
1000² = 1,000,000 = 1 million.
For large n, an n-step algorithm is generally faster than an n²-step one. · Pour de grands n, un algorithme en n étapes est généralement plus rapide qu'un algorithme en n² étapes.
n² grows much faster, so it does far more work at large n. · n² croît beaucoup plus vite, donc il effectue bien plus de travail à grand n.
We measure run time in seconds, which is the same on every computer. · Nous mesurons le temps d'exécution en secondes, ce qui est identique sur tous les ordinateurs.
We count operations vs. input size — seconds vary by machine. · Nous comptons les opérations par rapport à la taille de l'entrée — les secondes varient selon la machine.