Algorithmic Efficiency · Efficacité algorithmique
| English | Français |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | Efficacité algorithmique |
| slow/sləʊ/ | lente |
| steps/steps/ | étapes |
| reasonable/ˈriːzənəbl/ | raisonnable |
| unreasonable/ʌnˈriːzənəbl/ | irraisonnable |
| heuristic/hjuːˈrɪstɪk/ | heuristique |
Correct isn't always good enough
- Two algorithms can both be correct, yet one may be far better to use.
- Algorithmic efficiency 算法效率 compares algorithms by the resources they use — mainly time and memory.
- A correct-but-slow algorithm can be useless on large inputs.
- So we need a way to compare how they scale.
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 utilisent — 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: · L'efficacité algorithmique compare les algorithmes par :
Efficiency is about time and memory as input grows. · L'efficacité concerne le temps et la mémoire lorsque l'entrée augmente.
Counting steps as n grows
- Estimate the number of steps 步骤 an algorithm takes as its input size $n$ grows.
- A linear search takes about $n$ steps; a binary search about $\log_2 n$; comparing every pair about $n^2$.
- As $n$ gets large, these differences become huge.
- The shape of the growth matters far more than a stopwatch.
Compter les étapes quand n augmente
- Estimer 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.
How running time grows with n · La croissance du temps d'exécution avec 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. · Glissez n et comparez les courbes : log n reste presque plat, n monte régulièrement, n² explose. C'est pourquoi nous comparons les algorithmes par leur mise à l'échelle, pas avec un chronomètre.
Match each algorithm to its rough number of steps for input size n. · Faites correspondre chaque algorithme à son nombre approximatif d'étapes pour une taille d'entrée n.
These growth rates decide which algorithm scales. · Ces taux de croissance déterminent quel algorithme met à l'échelle.
Which growth is considered unreasonable as n gets large? · Quel taux de croissance est considéré comme irraisonnable lorsque n devient grand ?
Exponential growth quickly becomes far too slow. · La croissance exponentielle devient rapidement beaucoup trop lente.
When an exact answer is too slow, a ______ finds a good-enough solution fast. · Quand une réponse exacte est trop lente, une ______ trouve une solution suffisante rapidement.
A heuristic trades a perfect answer for speed. · Une heuristique échange une réponse parfaite pour la vitesse.
Reasonable vs unreasonable
- We separate a reasonable 合理 running time from an unreasonable 不合理 one.
- Roughly, growth like $n$ or $n^2$ is reasonable; doubling steps per extra item (like $2^n$) is not.
- When an exact answer is too slow, use a heuristic 启发式方法 — a good-enough solution found fast.
- Not perfect, but useful when perfect is impossible in time.
Raisonnable vs déraisonnable
- Nous distinguons un temps d'exécution raisonnable 合理 d'un temps déraisonnable 不合理.
- 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.
- Quand une réponse exacte est trop lente, utiliser 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) · Une recherche binaire de 1,000,000 éléments triés nécessite au maximum environ combien d'étapes ? (2^20 ≈ un million)
Because 2^20 is just over a million, ~20 halvings suffice. · Parce que 2^20 est juste au-dessus d'un million, ~20 halos suffisent.
A correct algorithm can still be too slow to use on large inputs. · Un algorithme correct peut encore être trop lent pour être utilisé sur de grandes entrées.
It must also finish in a reasonable time. · Il doit aussi se terminer dans un temps raisonnable.
Too slow to use
- This is why some correct algorithms are too slow 缓慢 to run in practice on large inputs.
- Being correct is not enough — an algorithm must also finish in a reasonable time.
A million items. A linear search of 1,000,000 sorted items may take up to 1,000,000 steps. A binary search takes at most about 20, because $2^{20}$ is just over a million. On small lists the gap barely matters; on a million items, binary is the only reasonable choice.
Trop lent à utiliser
- C'est pourquoi certains algorithmes corrects sont trop lents 缓慢 pour s'exécuter 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.
Algorithmic efficiency compares algorithms by resources as input size $n$ grows: linear $n$, binary $\log_2 n$, all-pairs $n^2$. Growth like $n$ or $n^2$ is reasonable; $2^n$ is unreasonable (use a heuristic). A correct algorithm that is too slow on large inputs is not good enough.
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.