Identifier la complexité temporelle d'une boucle

1) Repérer la structure de la boucle

Commence par observer les bornes de la boucle et la façon dont la variable d’itération change. La question essentielle est : combien de fois le corps de la boucle s’exécute quand la taille de l’entrée augmente ?

2) Relier la mise à jour à la croissance

À partir de la règle de mise à jour, estime le nombre d’itérations :

• Croissance linéaire : la variable avance d’une quantité fixe à chaque tour, donc la boucle s’exécute environ n fois → O(n).
• Travail constant : la boucle effectue un nombre fixe d’opérations, indépendant de la taille d’entrée → O(1).
• Boucles imbriquées : on multiplie le travail de la boucle interne par celui de la boucle externe si elles sont indépendantes.
• Multiplication ou division par 2 : le nombre d’itérations augmente lentement, souvent en log n → O(log n).

3) Simplifier la réponse finale

Ne garder que le terme dominant. Ignore les constantes et les termes de plus faible ordre. Par exemple, si le comptage donne 3n + 7, la complexité est O(n).

4) Vérifier le résultat

Demande-toi si la boucle demande clairement plus d’étapes quand la taille d’entrée augmente. Si doubler l’entrée double à peu près le travail, la réponse est probablement linéaire. Si le nombre d’étapes n’augmente que d’une unité quand l’entrée double, il s’agit probablement d’une complexité logarithmique.