Complexité Algorithmique
\( O(f(n)) \)
Notation Big O
Exemples de complexités :
O(1) - Constante
O(log n) - Logarithmique
O(n) - Linéaire
O(n log n) - Quasi-linéaire
O(n²) - Quadratique
O(log n) - Logarithmique
O(n) - Linéaire
O(n log n) - Quasi-linéaire
O(n²) - Quadratique
Définition :
Mesure de l'efficacité d'un algorithme en fonction de la taille des données
Classes de Complexité
O(1) - Temps constant
O(log n) - Croissance logarithmique
O(n) - Proportionnelle à la taille
O(n²) - Carrée de la taille
O(2ⁿ) - Exponentielle
Opérations Élémentaires
Affectation, opérations arithmétiques
Comparaisons
Accès aux éléments d'une structure
Méthodes & Conseils
Compter les instructions dans les boucles
Identifier les cas le pire
Ignorer les constantes multiplicatives
Considérer uniquement le terme dominant
Analyser la structure de contrôle
Code Exemple
# Recherche linéaire - O(n)
def recherche(tab, x):
for i in range(len(tab)):
if tab[i] == x:
return i
return -1# Tri à bulle - O(n²)
def tri_bulle(tab):
n = len(tab)
for i in range(n):
for j in range(0, n-i-1):
if tab[j] > tab[j+1]:
tab[j], tab[j+1] = tab[j+1], tab[j]Règles de Calcul
Règle de somme : O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
Règle de produit : O(f(n)) × O(g(n)) = O(f(n) × g(n))
Boucles imbriquées : O(n) × O(n) = O(n²)
Structures conditionnelles : O(max(branche))
Hiérarchie des Complexités
Ordre croissant d'efficacité :
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ)
Exemples concrets :
Accès tableau : O(1)
Recherche binaire : O(log n)
Parcours tableau : O(n)
Tri rapide : O(n log n)
Tri bulle : O(n²)
Recherche binaire : O(log n)
Parcours tableau : O(n)
Tri rapide : O(n log n)
Tri bulle : O(n²)
