Mille prix, presque cinq cent mille comparaisons
Un algorithme est une suite d’instructions précises qui résout un problème. La complexité dit combien d’étapes il demande quand les données grossissent, et elle sert à choisir le bon algorithme avant de l’écrire.
Une boutique en ligne veut repérer les prix en double dans son catalogue. Comparer chaque prix à tous les autres demande 499 500 comparaisons pour 1 000 prix. Pour 100 000 prix, il en faut près de cinq milliards.
À la fin de cette leçon
Remarque
Je peux compter les étapes d’un algorithme et dire comment ce nombre grandit.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Étape | une opération simple de l’algorithme | une comparaison |
| Complexité | la façon dont le nombre d’étapes grandit avec les données | |
| Constante | un nombre d’étapes qui ne change pas avec les données | |
| Linéaire | un nombre d’étapes qui grandit comme les données | |
| Quadratique | un nombre d’étapes qui grandit comme le carré des données | |
| Logarithmique | un nombre d’étapes qui grandit très lentement, en coupant en deux |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
On compte des étapes, pas des secondes
Pour comparer deux algorithmes, on ne mesure pas des secondes. Le temps dépend de l’ordinateur, de ce qu’il fait en même temps et même de sa chaleur.
On compte plutôt les étapes : des opérations simples comme une comparaison ou une addition. Ce nombre est exact et identique sur toutes les machines. On note n la taille des données, par exemple le nombre de prix dans la liste.
Exemple travaillé : le prix le plus bas
| Nombre de prix (n) | Comparaisons | Pourquoi |
|---|---|---|
| 6 | 5 | Le premier prix sert de départ, on compare les 5 autres |
| 10 | 9 | Toujours un de moins que n |
| 100 | 99 | Une comparaison par prix, sauf le premier |
| 1 000 000 | 999 999 | Le travail grandit en même temps que la liste |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Compter les étapes dans le code
# Chercher le prix le plus bas en comptant les étapes.
prix = [12, 7, 30, 9, 15, 8]
pas = 0
plus_bas = prix[0]
for p in prix[1:]:
pas = pas + 1 # une comparaison = une étape
if p < plus_bas:
plus_bas = p
print("plus bas :", plus_bas, "en", pas, "étapes")
# Ajoutez quatre prix à la liste, puis relancez.
Constante, linéaire, quadratique : trois formes de croissance
Lire le premier prix d’une liste prend une étape, que la liste ait dix ou un million de prix. C’est une complexité constante.
Parcourir toute la liste une fois fait n étapes : elle est linéaire. Comparer chaque paire de prix fait environ n fois n divisé par 2 étapes : elle est quadratique. Couper la liste en deux à chaque étape donne une complexité logarithmique, très lente à grandir.
Le nombre d’étapes selon la forme
| n | Constante | Logarithmique | Linéaire | Quadratique (n × n) |
|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 100 |
| 100 | 1 | 6 | 100 | 10 000 |
| 1 000 | 1 | 9 | 1 000 | 1 000 000 |
| 1 000 000 | 1 | 19 | 1 000 000 | 1 000 000 000 000 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Deux boucles imbriquées
# Deux boucles imbriquées : on compte les passages.
n = 6
pas = 0
for i in range(n):
for j in range(n):
pas = pas + 1
print("n =", n, "étapes =", pas)
# Mettez n à 12 : combien de fois plus d’étapes ?
Le labo compte, mais ne chronomètre pas
Dans le labo, chaque Run ci-dessous affiche un nombre exact qui découle de la ligne tapée. Le dernier utilise time, qui affiche trois durées. Ces durées changent d’une machine à l’autre et d’un essai à l’autre. Seul le résultat du calcul ne change jamais.
Une boucle de mille tours
python3 -c "exec('pas = 0\nfor i in range(1000):\n pas = pas + 1\nprint(pas)')"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Deux boucles de cent tours
python3 -c "exec('pas = 0\nfor i in range(100):\n for j in range(100):\n pas = pas + 1\nprint(pas)')"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Le résultat est fixe, la durée non
time python3 -c "print(sum(range(10000000)))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup pensent que l’algorithme qui fait le moins d’étapes sur 10 données est le meilleur. Ce qui compte, c’est comment le nombre d’étapes grandit. Un algorithme quadratique peut gagner sur 10 données et perdre sur 100 000. Comparez toujours pour de grandes valeurs de n.
On ne garde que le terme qui domine
Un algorithme fait parfois 3n + 5 étapes. Pour n = 1 000 000, les 5 étapes de plus ne changent rien : on dit qu’il est linéaire.
On garde seulement le terme qui grandit le plus vite et on oublie les multiples. On écrit alors O(n), qu’on lit « grand O de n ». Les quatre formes s’écrivent O(1), O(log n), O(n) et O(n²).