Plusieurs algorithmes pour un seul problème
Un algorithme est une suite d'étapes précises pour résoudre un problème. La plupart des problèmes peuvent être résolus par plus d'un algorithme. Par exemple, pour trouver un nom dans une liste, tu peux vérifier chaque nom, ou (si la liste est triée) tu peux la couper en deux encore et encore.
Les deux donnent la bonne réponse. La différence, c'est l'efficacité : la quantité de travail et de mémoire dont chacun a besoin. Un bon programmeur choisit l'algorithme qui reste rapide quand les données deviennent grandes.
Comparer les algorithmes selon le temps
Mesurer avec un chronomètre n'est pas juste : un ordinateur rapide fait paraître bon un algorithme lent. Alors on compte les étapes de base (comparaisons, échanges, additions) en fonction de la taille de l'entrée n.
Meilleur cas, cas moyen et pire cas
Le meilleur cas est l'entrée la plus chanceuse (13 est dans la première boîte : 1 étape). Le pire cas est la plus malchanceuse (13 n'y est pas : n étapes). On donne en général le pire cas, car c'est une promesse : l'algorithme ne sera jamais plus lent que cela.
Complexité en temps et complexité en espace
La complexité en temps dit comment le nombre d'étapes grandit avec n. La complexité en espace dit comment la mémoire supplémentaire grandit avec n. Le tri fusion est rapide mais demande de la mémoire en plus ; le tri à bulles n'en demande presque pas, mais il est lent.
La notation grand O
Le grand O décrit la vitesse de croissance en ignorant les petits détails. On garde seulement le terme le plus grand et on enlève les nombres constants : 3n² + 5n + 2 devient O(n²), car pour un grand n, la partie n² représente presque tout.
| Grand O | Nom | n = 16 | n = 1000 | Exemple |
|---|---|---|---|---|
| O(1) | constante | 1 | 1 | lire l'élément 5 d'un tableau |
| O(log n) | logarithmique | 4 | environ 10 | recherche dichotomique |
| O(n) | linéaire | 16 | 1000 | recherche linéaire, trouver le plus grand |
| O(n log n) | n log n | 64 | environ 10 000 | tri fusion |
| O(n²) | quadratique | 256 | 1 000 000 | tri à bulles, boucles imbriquées |
Règle rapide pour le code : une boucle sur n éléments est en O(n) ; une boucle dans une boucle est en O(n²) ; couper le problème en deux à chaque fois est en O(log n).
Efficacité de la recherche linéaire et dichotomique
La recherche linéaire vérifie les éléments un par un. Pire cas : n comparaisons, donc O(n). Elle marche sur n'importe quelle liste, triée ou non.
La recherche dichotomique demande une liste triée. On regarde l'élément du milieu ; s'il est trop grand, on jette la moitié de droite, sinon celle de gauche. Chaque étape coupe la liste en deux, donc le pire cas est d'environ log₂ n + 1 comparaisons : O(log n). Pour 1 000 000 d'éléments, cela fait environ 20 étapes au lieu de 1 000 000.
Efficacité des algorithmes de tri
Les tris à bulles, par insertion et par sélection utilisent une boucle dans une boucle, donc ils font environ n²/2 comparaisons : O(n²). Le tri par insertion est en O(n) dans le meilleur cas (une liste déjà triée).
Le tri fusion coupe la liste en deux environ log₂ n fois et fait environ n de travail à chaque niveau : O(n log n). Il demande O(n) de mémoire supplémentaire.
La recherche dichotomique demande une liste triée. Si tu ne cherches qu'une seule fois, trier d'abord (n log n) coûte plus cher qu'une seule recherche linéaire (n). Si tu cherches très souvent, trier une seule fois est rentable.
Préconditions, postconditions et pièges de la récursivité
Une précondition est ce qui doit être vrai avant le début de l'algorithme (recherche dichotomique : la liste est triée). Une postcondition est ce qui est garanti à la fin (tri : chaque élément est inférieur ou égal au suivant). Les écrire aide à tester et à prouver un algorithme.
La récursivité veut dire qu'une fonction s'appelle elle-même sur un problème plus petit. Erreurs fréquentes :
- Pas de cas de base, ou un cas de base jamais atteint : les appels ne s'arrêtent jamais (débordement de pile).
- Le problème ne diminue pas à chaque appel.
- Refaire le même travail : un Fibonacci récursif simple appelle fib(3) encore et encore, donc il grandit comme O(2ⁿ). Garder les réponses en mémoire (mémoïsation) le ramène à O(n).
- Une récursivité très profonde utilise beaucoup de mémoire, un cadre de pile par appel.
Essaie : une course entre deux recherches
Écris les nombres de 1 à 32 sur des bouts de papier et pose-les dans l'ordre, face cachée. Demande à un ami de choisir un nombre secret. Cherche d'abord un par un et compte les papiers retournés. Puis cherche en retournant toujours le papier du milieu. Recommence 5 fois. Quelle méthode n'a jamais eu besoin de plus de 6 retournements ? Vérifie avec le curseur de la dernière étape 3D (n = 32 : log₂ 32 = 5).
Formules et définitions clés
- Recherche linéaire : pire cas n comparaisons → O(n)
- Recherche dichotomique : pire cas environ log₂ n + 1 comparaisons → O(log n)
- Tri à bulles / insertion / sélection : environ n(n − 1)/2 comparaisons → O(n²)
- Tri fusion : environ n log₂ n comparaisons → O(n log n)
- Règle du grand O : garde le plus grand terme, enlève les constantes (5n² + 3n → O(n²))
- Si n double : O(1) pareil, O(log n) +1, O(n) ×2, O(n²) ×4
Exemples résolus
1. Une liste contient 50 noms. Combien de comparaisons la recherche linéaire demande-t-elle dans le meilleur et le pire cas ?
Meilleur cas : le nom est en premier → 1 comparaison. Pire cas : le nom est en dernier ou absent → 50 comparaisons. La recherche linéaire est en O(n).
2. Quel est le plus grand nombre de comparaisons de la recherche dichotomique pour une liste triée de 1024 éléments ?
Chaque étape coupe la liste en deux : 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. Cela fait 10 divisions par deux, plus la dernière vérification : au plus 11 comparaisons (log₂ 1024 = 10).
3. Donne le grand O de f(n) = 4n² + 10n + 7.
Garde le plus grand terme (4n²) et enlève la constante 4 : O(n²).
4. Une boucle fait varier i de 1 à n, et à l'intérieur une autre boucle fait varier j de 1 à n. Combien de fois la ligne intérieure s'exécute-t-elle ?
n fois pour chacune des n valeurs de i : n × n = n². Complexité en temps O(n²).
5. Un programme en O(n²) trie 1000 éléments en 2 secondes. Environ combien de temps pour 3000 éléments ?
n devient 3 fois plus grand, donc n² devient 3² = 9 fois plus grand : environ 2 × 9 = 18 secondes.
6. Compare le tri à bulles et le tri fusion pour n = 1000 éléments.
Tri à bulles : environ n²/2 = 500 000 comparaisons. Tri fusion : environ n log₂ n = 1000 × 10 = 10 000. Le tri fusion fait environ 50 fois moins de travail, mais il demande de la mémoire en plus.
Erreurs fréquentes
- Mesurer la vitesse seulement avec un chronomètre sur un seul ordinateur. Compte plutôt les étapes en fonction de n.
- Utiliser la recherche dichotomique sur une liste non triée. Sa précondition est une liste triée.
- Garder les constantes dans le grand O, par exemple écrire O(2n). C'est simplement O(n).
- Écrire une fonction récursive sans cas de base, ou qui ne rend pas le problème plus petit.