Algorithmic efficiency · Efficacité algorithmique
What we'll do
- Two programs can both be correct but take very different time.
- This lesson is about efficiency: how the work grows as the input grows.
- Read and think about the ideas; then a few short tasks let you count the steps yourself.
Ce que nous allons faire
- Deux programmes peuvent tous deux être corrects mais prendre des temps très différents.
- Cette leçon porte sur l'efficacité : comment le travail augmente lorsque l'entrée augmente.
- Lisez et réfléchissez aux idées ; ensuite, quelques petites tâches vous permettent de compter les étapes vous-même.
Counting the work
- We measure an algorithm by how many steps it does, not seconds.
- Steps in seconds depend on the computer; counting steps does not.
- More input usually means more steps. The question is how much more.
Compter le travail
- Nous mesurons un algorithme par combien d'étapes il effectue, pas en secondes.
- Les étapes en secondes dépendent de l'ordinateur ; compter les étapes non.
- Plus d'entrées signifient généralement plus d'étapes. La question est combien de plus.
Reasonable vs unreasonable run time
- Some algorithms grow slowly: double the input, do about double the work.
- Some algorithms grow fast: a little more input means a huge jump in work.
- "Reasonable" run time grows slowly enough to finish; "unreasonable" blows up.
Temps d'exécution raisonnable vs irraisonnable
- Certains algorithmes croissent lentement : doublez l'entrée, faites environ le double du travail.
- Certains algorithmes croissent vite : un peu plus d'entrée signifie un bond énorme dans le travail.
- Un temps d'exécution "raisonnable" croît lentement assez pour se terminer ; "irraisonnable" explose.
Input size: 10 20 40
Search a list: 10 20 40 (slow growth - reasonable)
Try all orders: 3,628,800 ... a number with 48 digits (explodes!)
A tiny demo: counting steps
- Below we count the comparisons a linear search makes.
- The count grows in step with the list size — slow, steady growth.
- Try changing the size to see the count follow it.
Une petite démo : compter les étapes
- Ci-dessous, nous comptons les comparaisons qu'une recherche linéaire effectue.
- Le compte augmente au rythme de la taille de la liste — croissance lente et constante.
- Essayez de changer la taille pour voir le compte la suivre.
def count_steps(n):
steps = 0
data = list(range(n))
target = -1 # not in the list, so we scan everything
for item in data:
steps = steps + 1
if item == target:
break
return steps
print(count_steps(10))
print(count_steps(20))
print(count_steps(40))
When fast is not enough
- Some problems have no known fast algorithm.
- The only methods try a huge number of possibilities — too slow for big input.
- For these, we often accept a good-enough answer instead of the perfect one.
Quand la rapidité ne suffit pas
- Certains problèmes n'ont aucun algorithme rapide connu.
- Les seules méthodes essayent un grand nombre de possibilités — trop lent pour les grandes entrées.
- Pour ceux-ci, nous acceptons souvent une réponse suffisamment bonne au lieu de la parfaite.
Undecidable problems
- Worse than slow: some problems cannot be solved by any algorithm at all.
- These are called undecidable problems.
- No matter how fast computers get, no program can always give the right answer.
Problèmes indécidables
- Pire que lent : certains problèmes ne peuvent pas être résolus par aucun algorithme du tout.
- On les appelle des problèmes indécidables.
- Peu importe à quelle vitesse les ordinateurs deviennent rapides, aucun programme ne peut toujours donner la bonne réponse.
Fast : finishes quickly, even for big input
Slow but doable : finishes, but may take a very long time
Undecidable : no algorithm can solve it for every input
Key ideas to remember
- Efficiency is about how work grows with input size.
- Slow-growing algorithms scale to big inputs; fast-growing ones do not.
- Some problems are unreasonable to solve exactly, and some are undecidable.
Idées clés à retenir
- L'efficacité concerne la façon dont le travail croît avec la taille de l'entrée.
- Les algorithmes à croissance lente s'échellonnent vers les grandes entrées ; ceux à croissance rapide non.
- Certains problèmes sont irraisonnables à résoudre exactement, et d'autres sont indécidables.
Common mistakes
- Big-O describes how the running time GROWS with the input size.
- A reasonable-time algorithm scales; an unreasonable one does not.
Erreurs courantes
- Big-O décrit comment le temps d'exécution CROÎT avec la taille de l'entrée.
- Un algorithme à temps raisonnable s'échelle ; un irraisonnable non.
Now you try
- Write small functions that count steps to feel how the work grows.
- Compare a single loop, a nested loop, and "try all orders". Press Check answer.
À vous maintenant
- Écrivez de petites fonctions qui comptent les étapes pour ressentir comment le travail croît.
- Comparez une boucle unique, une boucle imbriquée et "essayer tous les ordres". Appuyez sur Check answer.
How algorithms scale · Comment les algorithmes évoluent
As input grows, O(n²) explodes while O(log n) barely moves. · Lorsque l'entrée augmente, O(n²) explose tandis que O(log n) bouge à peine.
Write scan_compares(data, target) that returns how many comparisons a linear search makes. Compare each item to target, counting one each time, and stop as soon as you find it. If it is not in the list, you compared every item. Example: scan_compares([5, 8, 2], 8) → 2. · Écrivez scan_compares(data, target) qui retourne combien de comparaisons effectue une recherche linéaire. Comparez chaque élément à target, en comptant un à chaque fois, et arrêtez dès que vous le trouvez. S'il n'est pas dans la liste, vous avez comparé tous les éléments. Exemple : scan_compares([5, 8, 2], 8) → 2.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write pair_count(n) that uses a loop inside a loop (both over range(n)) and returns how many times the inner step runs. This is n × n. Example: pair_count(3) → 9. This grows much faster than a single loop. · Écrivez pair_count(n) qui utilise une boucle dans une boucle (toutes deux sur range(n)) et retourne combien de fois l'étape intérieure s'exécute. C'est n × n. Exemple : pair_count(3) → 9. Cela croît beaucoup plus vite qu'une seule boucle.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write count_orderings(n) that returns how many different orders n items can be placed in — that is 1 × 2 × ... × n (n factorial). count_orderings(0) is 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million. · Écrivez count_orderings(n) qui retourne combien d'ordres différents n éléments peuvent prendre — c'est-à-dire 1 × 2 × ... × n (factorielle de n). count_orderings(0) est 1. Exemple : count_orderings(3) → 6. Remarquez à quel point cela explose vite : count_orderings(10) est supérieur à 3 millions.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.