Cette carte explique comment se calcule le coût d’un algorithme : combien d’opérations il fait en fonction de la taille des données, n, et comment il croît quand n croît.
Le coût est une fonction de n. Les secondes dépendent de l’ordinateur ; les opérations, non.
Clique sur chaque cadre pour voir son explication. Les flèches ← → (ou les boutons du bas) passent au suivant et Échap la ferme. Une fois vu, un ✓ apparaît ; clique dessus pour l’enlever. Les cadres avec « ? » sont d’autres niveaux.
Cette carte explique comment se calcule le coût d’un algorithme : combien d’opérations fait un programme. Chaque cadre a une courte explication et, dans certains cas, un exercice.
Un algorithme est plus rapide quand il fait moins d’opérations.
Clique sur chaque cadre pour voir son explication. Les flèches ← → passent au suivant et Échap la ferme. Une fois vu, un ✓ apparaît.
4e année d’ESO (pour les plus avancés). Version simplifiée : règles de calcul, ordre par rapport à n et recherche dichotomique. Sans notation O(·) formelle, sans graphiques des algorithmes et sans le cadre des opérations.
S’intègre à : Numérique 4e (pensée informatique : critères 3.1 et 3.2, algorithmes logiques et efficaces).
Activité suggérée : compter les opérations d’une boucle puis vérifier avec la recherche dichotomique combien d’étapes elle fait.
PTD-I · 1re année de Baccalauréat. On ajoute les règles de calcul (séquence, conditionnelle et boucle), la notation O(·), les graphiques de croissance et de temps, la recherche linéaire et le tri par sélection. Les expériences de temps (ms) cessent d’être au centre : ce que l’on mesure, c’est le nombre d’opérations.
S’intègre à : Programmation et traitement des données I : CEsp1 (analyse et conception d’algorithmes, critère 1.3 sur le coût informatique) et CEsp3 (efficacité et complexité des opérations sur les structures de données).
Activité suggérée : avec 10⁹ opérations par seconde et n = 10⁶, calculer combien de temps mettraient la recherche linéaire (n) et le tri à bulles (n(n−1)/2), et comparer avec le graphique du temps.
PTD-II · 2e année de Baccalauréat. Même contenu que PTD-I : règles de calcul, notation O(·), graphiques de croissance et algorithmes de recherche et de tri.
S’intègre à : Programmation et traitement des données II : CEsp1 (algorithmes et pensée informatique).
Activité suggérée : comparer à la main la recherche linéaire et la dichotomique avec n = 1 000 000 et justifier la différence.
Les cadres avec «?» sont cachés à ce niveau : un clic les découvre et montre leur relation, un autre ouvre la fenêtre et, après l’avoir vue, un autre clic les cache de nouveau. Le bouton 🔗 copie un lien avec le niveau et les cadres découverts.
Le sélecteur Niveau change la carte et toutes les fenêtres. L’adresse conserve le niveau (?edad=4eso, ptd1 ou ptd2) et les cadres découverts (&ver=casos,fonts).
Quand on dit qu’un algorithme est rapide, il faut dire rapide en quoi. Les secondes dépendent de l’ordinateur, du système et de ce qui s’exécute. C’est pourquoi on compte opérations.
Quand tu compares deux algorithmes, demande-toi : ce qui croît et de combien?
Le coût informatique mesure le travail d’un programme selon la taille des données (n. Regarde deux choses : le temps (nombre d’opérations) et la mémoire (l’espace qu’elle occupe).
Le coût informatique d’un algorithme est le nombre d’opérations élémentaires qu’il fait, en fonction de la taille des données, n. Les secondes dépendent de l’ordinateur ; les opérations, non.
Une opération élémentaire (affectation, addition, comparaison ou accès à une position) coûte 1. On compte le pire cas, ce qui garantit le résultat pour n’importe quelle donnée.
| Fonction T(n) | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| n | 10 | 1 000 | 1 000 000 |
| n² | 100 | 1 000 000 | 1 000 000 000 000 |
Les secondes ne servent pas à comparer des algorithmes. Compte opérations et regarde comment croissent quand n croît.
La taille n. Toutes les formules dépendent d’une taille, n: le nombre de données que reçoit l’algorithme. Définis n avant de compter (nombre d’éléments, de chiffres ou de lignes, selon le problème).
Un programme exécute des instructions les unes après les autres. Pour calculer le coût, additionne les instructions. S’il y a une boucle, multiplie par le nombre de répétitions.
Une instruction simple coûte 1. Une boucle multiplie le coût de son corps par le nombre de répétitions.
Un programme combine quatre structures. Le coût total se calcule en appliquant une règle à chacune.
| Structure | Règle de coût | Exemple |
|---|---|---|
| Instruction simple | 1 | x ← x + 1 → 1 |
| Séquence | somme des coûts | A ; puis B → T(A) + T(B) |
| Conditionnelle | test + le chemin le plus coûteux | si … alors … sinon … → 1 + max(T₁, T₂) |
| Boucle | itérations × coût du corps | pour i de 1 à n : x ← x + 1 → n |
Quand tu ne sais pas quelle branche d’une conditionnelle s’exécutera, prends la plus coûteuse : c’est le pire cas.
Le coût d’une boucle est le coût de son corps multiplié par le nombre de répétitions. Une opération ne se remarque pas ; un million, si.
| Structure | Opérations avec n = 1 000 | Opérations avec n = 1 000 000 |
|---|---|---|
| Une boucle | 1 000 | 1 000 000 |
| Deux boucles imbriquées | 1 000 000 | 1 000 000 000 000 |
Compte combien de fois s’exécute le corps le plus interne. Une boucle de n étapes fait n opérations ; deux boucles imbriquées de n étapes font n · n.
Deux boucles imbriquées sont O(n²); une boucle, O(n).
Une structure qui semble simple (« ce n’est qu’une boucle ») peut cacher une recherche à l’intérieur. Regarde toujours ce qu’il y a dans la boucle.
Une boucle répète son corps. Le coût total est le coût du corps multiplié par le nombre de répétitions.
| Structure | Opérations avec n = 1 000 | Opérations avec n = 1 000 000 |
|---|---|---|
| Une boucle | 1 000 | 1 000 000 |
| Deux boucles imbriquées (n · n) | 1 000 000 | 1 000 000 000 000 |
| Deux boucles, la seconde jusqu’à i | 500 500 | 500 000 500 000 |
Une boucle est O(n). Deux boucles imbriquées sont O(n²). Les boucles imbriquées qui vont jusqu’à i font n(n+1)/2 étapes : aussi O(n²), car nous ignorons la constante ½.
Une structure qui semble simple (« ce n’est qu’une boucle ») peut cacher une recherche à l’intérieur. Regarde toujours ce qu’il y a dans la boucle.
Le tri à bulles compare les voisins et les échange s’ils sont dans le mauvais ordre. Il répète les passages jusqu’à ne plus rien échanger. C’est l’algorithme typique pour comprendre le coût, car on peut tout compter.
| n (données) | Comparaisons (pire cas) | Échanges (moyenne) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
Chaque passage place la plus grande valeur à la fin. Avec n données, le premier passage fait n−1 comparaisons, le suivant n−2, et ainsi de suite jusqu’à 1. En tout, dans le pire cas : n(n−1)/2.
Remarque : si tu multiplies les données par 10, le travail est multiplié par 100.
Cela est O(n²). Les comparaisons croissent comme le carré de n.
Le tri à bulles compare chaque paire de voisins et échange ceux qui sont mal ordonnés. Après chaque passage, la plus grande valeur reste à la fin.
| n (données) | Comparaisons (pire cas) | Échanges (moyenne) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
Le premier passage fait n−1 comparaisons, le deuxième n−2, et ainsi de suite jusqu’à 1. Total dans le pire cas : (n−1) + (n−2) + … + 1 = n(n−1)/2, c’est-à-dire O(n²).
Graphique du temps : le temps est proportionnel au nombre d’opérations. Avec 10⁹ opérations par seconde, 10⁶ opérations prennent 1 ms.
Si la liste est triée, inutile de la regarder en entier. Tu regardes le milieu et tu écartes la moitié qui ne peut pas contenir ce que tu cherches. Chaque étape réduit la taille de moitié.
La liste est 1, 2, 3… n : pas besoin de la garder entièrement en mémoire, c’est pourquoi on peut tester avec 1 000 000 000.
| n (données) | Étapes dichotomique (pire cas) | Comparaisons linéaire (pire cas) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Chaque étape fait une comparaison et élimine la moitié. Les étapes sont environ log₂ n. C’est pourquoi 1 000 000 000 de données n’ont besoin que de 30 étapes.
Cela est O(log n).
La dichotomique ne fonctionne que si la liste est triée. La trier a aussi un coût.
La recherche dichotomique regarde le milieu de la liste triée et écarte la moitié qui ne peut pas contenir ce que tu cherches. Chaque étape divise par 2.
La liste est 1, 2, 3… n. On ne compte que les étapes : pas besoin de la garder en mémoire.
| n (données) | Étapes (pire cas) | Recherche linéaire (pire cas) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Chaque étape réduit la taille de moitié : après k étapes il reste n / 2ᵏ éléments. Comme n / 2ᵏ = 1 quand k = log₂ n, le coût est O(log n).
La recherche dichotomique ne fonctionne que si la liste est triée. La trier a aussi un coût.
Graphique du temps : le temps est proportionnel au nombre d’opérations. Avec 10⁹ opérations par seconde, 10⁶ opérations prennent 1 ms.
Quand les données croissent, le coût croît à un rythme donné. La notation O(·) ne garde que ce rythme et ignore les constantes.
O(log n) croît très lentement : quand n passe de 1 à 20, il n’atteint que ≈ 4,3, alors que O(n) atteint 20.
Avec un petit n, toutes les courbes semblent proches ; à partir de n ≈ 10 la quadratique se sépare des autres.
| Fonction | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| O(log n) | ≈ 3 | ≈ 10 | ≈ 20 |
| O(n) | 10 | 1 000 | 1 000 000 |
| O(n log n) | ≈ 33 | ≈ 10 000 | ≈ 20 000 000 |
| O(n²) | 100 | 1 000 000 | 1 000 000 000 000 |
O(1) : le coût ne dépend pas de n. O(log n) : chaque étape divise par 2 (dichotomique). O(n) : proportionnel à n (recherche linéaire). O(n log n) : typique des bons algorithmes de tri. O(n²) : deux boucles imbriquées (tri à bulles, tri par sélection).
Quand n est multiplié par 10 : avec O(n) le coût est multiplié par 10 ; avec O(n²), par 100 ; avec O(log n), il ne change presque pas.
Ignore les constantes et les termes petits : 3n² + 5n est O(n²).
L’ordre par rapport à n explique comment le coût croît quand les données croissent. C’est l’idée la plus importante de cette carte.
Quand n est multiplié par 10, un coût O(n) est aussi multiplié par 10, mais un coût O(n²) est multiplié par 100.
Si le coût est O(n), le travail croît comme les données. S’il est O(n²), avec le double de données le travail est multiplié par quatre.
Ce qui compte, c’est comment croît, pas le nombre exact d’opérations.
Le même algorithme peut prendre plus ou moins de temps selon les données. C’est pourquoi l’analyse distingue trois cas : meilleur, moyen et pire.
| Cas | Tri à bulles | Dichotomique |
|---|---|---|
| Meilleur | n−1 comparaisons (liste déjà triée) | 1 étape (le milieu est celui cherché) |
| Moyen | ≈ n²/2 comparaisons | ≈ log₂ n étapes |
| Pire | n(n−1)/2 comparaisons | ⌊log₂ n⌋ + 1 étapes |
Si le quotient est proche de 2, la croissance est à peu près linéaire ; s’il est proche de 4, quadratique. Le bruit du navigateur empêche l’exactitude : c’est pourquoi on prend la médiane de 3 répétitions.
Pour évaluer un algorithme, il faut regarder les données de pire cas (celles qui le font travailler le plus), mais aussi le cas moyen, qui est généralement le plus courant.
Une seule mesure d’un cas particulier ne dit pas quel est le pire. Analyse le cas, puis mesure.
La recherche linéaire examine les éléments un par un jusqu’à trouver ce que tu cherches. C’est la méthode la plus simple et elle sert de référence pour comparer avec la recherche dichotomique.
Chaque élément est comparé à la valeur cherchée jusqu’à la trouver ou atteindre la fin.
| Cas | Comparaisons | Avec n = 1 000 000 |
|---|---|---|
| Meilleur (c’est le premier) | 1 | 1 |
| Moyen (il est au milieu) | n / 2 | 500 000 |
| Pire (c’est le dernier ou il n’y est pas) | n | 1 000 000 |
Le coût est O(n): chaque élément est examiné au plus une fois.
Quand tu donnes un coût, dis quel cas est : le meilleur, le moyen ou le pire.
Graphique du temps : le temps est proportionnel au nombre d’opérations. Avec 10⁹ opérations par seconde, 10⁶ opérations prennent 1 ms.
Le tri par sélection cherche le minimum de la partie non triée et le place devant. Répète jusqu’à ce que toute la liste soit triée.
Le premier passage cherche le minimum parmi n éléments (n−1 comparaisons) et le place en première position. Le suivant cherche parmi n−1 éléments, et ainsi de suite jusqu’au dernier.
| n (données) | Comparaisons (toujours) |
|---|---|
| 10 | 45 |
| 100 | 4 950 |
| 1 000 | 499 500 |
Total : (n−1) + (n−2) + … + 1 = n(n−1)/2, c’est-à-dire O(n²) dans tous les cas. Il fait au plus n−1 échanges.
Le tri par sélection fait toujours les mêmes comparaisons ; le tri à bulles peut s’arrêter plus tôt si la liste est déjà triée.
Graphique du temps : le temps est proportionnel au nombre d’opérations. Avec 10⁹ opérations par seconde, 10⁶ opérations prennent 1 ms.
Le tri par insertion prend chaque élément et le place à sa juste position dans la partie déjà triée.
Dans le pire cas (liste inversée) fait n(n−1)/2 comparaisons : O(n²). Dans le meilleur cas (liste déjà triée) n’en fait que n−1 : O(n).
Le tri par insertion est rapide quand la liste est déjà presque triée.
Le tri fusion coupe la liste en deux, trie chaque moitié, puis les fusionne.
Chaque niveau de divisions fait n étapes et il y a log₂ n niveaux. Le coût est O(n log n) dans tous les cas.
Pour les grandes listes, elle est beaucoup plus rapide que le tri à bulles.
Mesurer est facile à mal faire. Voici les erreurs les plus courantes et comment les éviter.
Avant de dire qu’un algorithme est plus rapide, demande-toi : avec quelles données, sur quelle machine et combien de fois je l’ai mesuré.
Lis chaque situation et choisis quel concept explique le cas. Si tu en choisis un qui y figure aussi mais qui n’est pas le principal, nous te le dirons.
Un programme additionne 1 000 000 de nombres dans une boucle. Quel concept explique pourquoi le coût est élevé ?
Un programme additionne 1 000 000 de nombres dans une boucle. Quel concept explique pourquoi le coût est élevé ?
Tu cherches le nombre 42 dans une liste triée d’un million de nombres. Tu regardes le milieu, tu écartes la moitié et, en une vingtaine d’étapes, tu le trouves. Quel algorithme est-ce ?
Un algorithme parcourt la liste en comparant les voisins et en les échangeant. Avec la liste inversée il fait n(n−1)/2 comparaisons. Quel algorithme est-ce ?
Un algorithme met 4 fois plus de temps quand tu doubles les données. Quel concept décrit la croissance de son coût ?
Tu cherches un nombre dans une liste non triée de n éléments et tu le compares à chaque élément jusqu’à le trouver. Quel algorithme est-ce ?
Un algorithme cherche le minimum de la partie non triée et le place devant. Il fait n(n−1)/2 comparaisons même si la liste est déjà triée. Quel algorithme est-ce ?
Cette carte réunit des concepts classiques de l’analyse d’algorithmes et les objectifs du programme des Îles Baléares. Voici où le vérifier et aller plus loin.