Méthode de comptage des pas
La méthode de comptage des pas est l'une des techniques les plus utilisées pour analyser la complexité temporelle d'un algorithme.
Elle consiste à compter combien de fois chaque instruction est exécutée, puis à sommer les coûts pour obtenir une fonction \(T(n)\) dépendant de la taille n de l'entrée.
L'objectif est de déterminer l'ordre de grandeur de \(T(n)\), c'est-à-dire son comportement asymptotique.
Principe de la méthode
- Identifier les instructions élémentaires (lecture, affectation, comparaison, etc.).
- Compter combien de fois chaque instruction est exécutée, en fonction de n.
- Multiplier par le coût de l'instruction (souvent supposé constant).
- Additionner tous les coûts pour obtenir la fonction \(T(n)\).
- Simplifier (on ne garde que le terme dominant).
Règle maximale
Si un algorithme est constitué de plusieurs blocs exécutés séquentiellement, le temps total est dominé par le bloc le plus coûteux.
\[ T(n) = \max(T_A(n), T_B(n), \dots) \]
Exemple
if condition:
# bloc A : O(1)
else:
# bloc B : O(n)Complexité totale = \(\max(O(1), O(n)) = O(n)\)
Cas des instructions simples
Une instruction simple (sans boucle ni appel récursif) a une complexité constante.
Exemple
a = 2
b = 3 + 4
c = a * b - 2Chacune est exécutée une seule fois → \(O(1)\)
Cas des appels de fonctions
- Si la fonction contient uniquement des instructions simples → \(O(1)\).
- Si elle contient une boucle ou un appel récursif → la complexité de la fonction est celle de son corps.
Structures conditionnelles (if – else – elif)
On applique la règle maximale :
\[ T(n) = \max(T(\text{branche 1}), T(\text{branche 2}), \dots) \]
Exemple
if cond1: # O(1)
...
elif cond2: # O(n^2)
...
else: # O(n)
...Complexité = \(\max(O(1), O(n^2), O(n)) = O(n^2)\)
Tableau récapitulatif des règles
| Structure | Règle de comptage | Exemple | Complexité |
|---|---|---|---|
| Instruction simple | Exécutée une fois | a = b + c | \(O(1)\) |
| Séquence d'instructions | Somme des coûts | instr1 + instr2 + instr3 | \(O(f_1 + f_2 + f_3)\) |
| Conditionnelle (if-else) | Maximum des branches | if A else B | \(\max(O(A), O(B))\) |
| Appel de fonction | Coût de la fonction appelée | f(x) avec f contenant une boucle | \(O(\text{corps de f})\) |
La méthode de comptage des pas est une technique systématique pour analyser la complexité temporelle d'un algorithme :
- On identifie les instructions élémentaires et on compte leur nombre d'exécutions.
- On applique les règles : somme pour les séquences, max pour les conditionnelles, produit pour les boucles imbriquées.
- On simplifie en ne gardant que le terme dominant pour obtenir la notation asymptotique \(O\).
Cette méthode permet de comparer objectivement l'efficacité des algorithmes indépendamment des détails d'implémentation.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.