Complexité algorithmique
Estimer le coût d’un algorithme à partir de la taille de l’entrée et du cas étudié.
1
Mesurer l’entrée
Définition rapide
La taille d’entrée est le nombre d’éléments traités par l’algorithme.
- On note souvent
nla taille de l’entrée. - Elle dépend du problème étudié.
Exemples
| Entrée | Taille | Repère |
|---|---|---|
| Tableau | Nombre d’éléments | n |
| Chaîne | Longueur | n |
| Graphe | Sommets ou arêtes | Selon le contexte |
2
Coût et grand O
Idée centrale
La notation grand O décrit une borne supérieure asymptotique du coût quand n grandit.
Repères d’ordre
- On compte des opérations élémentaires.
- On garde l’ordre dominant.
Mémo
==O = ordre de grandeur==, pas valeur exacte. Un facteur constant ne change pas l’ordre.
3
Comparer les cas
Contraste
Meilleur cas
- Entrée la plus favorable.
- Coût minimal possible.
- Utile pour savoir le minimum.
Pire cas
- Entrée la plus défavorable.
- Borne de garantie.
- Souvent retenu pour raisonner.
Cas moyen
Le cas moyen décrit le comportement moyen sur les entrées possibles.
- Il peut être différent du meilleur et du pire cas.
- Il demande souvent une hypothèse sur les entrées.
Piège fréquent
Ne pas confondre cas moyen et pire cas. Toujours préciser le cas étudié.
4
Boucles et ordre de grandeur
Règles rapides
- 1
Une boucle simple sur
néléments donne souvent - 2
Des boucles imbriquées donnent souvent un produit
Estimation rapide
Point d’attention
Toute boucle imbriquée n’est pas forcément `O(n²)`. Il faut analyser ses bornes.
5
Algorithmes usuels
Réflexes
- Parcours d’un tableau : souvent
O(n). - Recherche dichotomique : souvent
O(log n).
Mini-défi
- Dire la taille d’entrée d’une chaîne.
- Donner l’ordre d’une boucle simple sur
néléments.
Résumé
- La taille d’entrée se note souvent
n. - Le coût est exprimé par le grand O.