Algorithmic Efficiency
Introduit| English | Sens |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | efficacité algorithmique |
| slow/sləʊ/ | lent |
| steps/steps/ | étapes |
| reasonable/ˈriːzənəbl/ | raisonnable |
| unreasonable/ʌnˈriːzənəbl/ | irraisonnable |
| heuristic/hjuːˈrɪstɪk/ | heuristique |
Correct n'est pas toujours suffisant
- Deux algorithmes peuvent tous deux être corrects, mais l'un peut être bien meilleur à utiliser.
- L'efficacité algorithmique compare les algorithmes par les ressources qu'ils consomment — principalement le temps et la mémoire.
- Un algorithme correct mais lent peut être inutilisable sur de grandes entrées.
- Nous avons donc besoin d'un moyen de comparer comment ils évoluent.
Algorithmic efficiency compares algorithms by:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Efficiency is about time and memory as input grows.
Compter les étapes quand n augmente
- Estimez le nombre d'étapes qu'un algorithme effectue lorsque la taille de son entrée $n$ augmente.
- Une recherche linéaire prend environ $n$ étapes ; une recherche binaire environ $\log_2 n$ ; comparer chaque paire environ $n^2$.
- Quand $n$ devient grand, ces différences deviennent énormes.
- La forme de la croissance est bien plus importante qu'un chronomètre.

Comment le temps d'exécution d'un algorithme augmente avec la taille de l'entrée n
How running time grows with n
Slide n and compare the curves: log n stays almost flat, n rises steadily, n² explodes. This is why we compare algorithms by how they scale, not with a stopwatch.
Match each algorithm to its rough number of steps for input size n.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
These growth rates decide which algorithm scales.
Which growth is considered unreasonable as n gets large?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Exponential growth quickly becomes far too slow.
When an exact answer is too slow, a ______ finds a good-enough solution fast.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
A heuristic trades a perfect answer for speed.
Raisonnable vs déraisonnable
- Nous distinguons un temps d'exécution raisonnable d'un temps irraisonnable.
- Grossièrement, une croissance comme $n$ ou $n^2$ est raisonnable ; un doublement des étapes par élément supplémentaire (comme $2^n$) ne l'est pas.
- Lorsqu'une réponse exacte est trop lente, utilisez une heuristique — une solution suffisante trouvée rapidement.
- Pas parfaite, mais utile quand le parfait est impossible dans les délais.
A binary search of 1,000,000 sorted items needs at most about how many steps? (2^20 ≈ a million)
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Because 2^20 is just over a million, ~20 halvings suffice.
If an algorithm is correct, it will always run fast enough on large inputs.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
False. A correct algorithm can still be too slow on large inputs; it must also finish in a reasonable time.
Trop lent à utiliser
- C'est pourquoi certains algorithmes corrects sont trop lents pour être exécutés en pratique sur de grandes entrées.
- Être correct ne suffit pas — un algorithme doit aussi se terminer dans un temps raisonnable.
Un million d'éléments. Une recherche linéaire de 1,000,000 éléments triés peut prendre jusqu'à 1,000,000 étapes. Une recherche binaire prend au maximum environ 20, car $2^{20}$ est légèrement supérieur à un million. Sur de petites listes, l'écart a peu d'importance ; sur un million d'éléments, la recherche binaire est le seul choix raisonnable.
L'efficacité algorithmique compare les algorithmes par ressources lorsque la taille de l'entrée $n$ croît : linéaire $n$, binaire $\log_2 n$, toutes-paires $n^2$. Une croissance comme $n$ ou $n^2$ est raisonnable ; $2^n$ est irraisonnable (utiliser une heuristique). Un algorithme correct mais trop lent sur de grandes entrées n'est pas suffisant.