Complexité algorithmique : Mesure de la quantité de ressources (temps ou espace) nécessaire à un algorithme.
- Identifier les opérations élémentaires
- Compter leur nombre en fonction de la taille des données
- Exprimer la complexité en notation O
fonction somme(n):
resultat ← 0
pour i de 1 à n:
resultat ← resultat + i
retourner resultatL'instruction resultat ← 0 s'exécute 1 fois : O(1)
La boucle pour s'exécute n fois
Chaque itération contient une addition : O(1)
O(1) + n × O(1) = O(1) + O(n) = O(n)
On néglige les constantes et termes d'ordre inférieur
La complexité temporelle de la fonction somme(n) est O(n).
• Boucles simples : Si une boucle s'exécute n fois, complexité O(n)
• Opérations élémentaires : Assignations, additions, comparaisons sont O(1)
• Simplification : On garde le terme dominant dans la notation O
Tri à bulles : Algorithme de tri qui compare les éléments adjacents et les échange si nécessaire.
fonction triBulle(tableau, n):
pour i de 0 à n-2:
pour j de 0 à n-2-i:
si tableau[j] > tableau[j+1]:
echanger(tableau[j], tableau[j+1])La boucle externe s'exécute (n-1) fois : O(n)
La boucle interne s'exécute environ n-i fois pour chaque i
Moyenne sur toutes les itérations : ≈ n/2 fois
O(n) × O(n) = O(n²)
La complexité temporelle du tri à bulles est O(n²).
• Boucles imbriquées : Multiplier les complexités des boucles
• Complexité quadratique : Se produit souvent avec des algorithmes à deux dimensions
• Comparaison : O(n²) devient inefficace pour grandes valeurs de n
Recherche binaire : Algorithme qui divise l'espace de recherche par 2 à chaque étape.
fonction rechercheBinaire(tableau, element):
debut ← 0
fin ← taille(tableau) - 1
tant que debut ≤ fin:
milieu ← (debut + fin) / 2
si tableau[milieu] = element:
retourner milieu
sinon si tableau[milieu] < element:
debut ← milieu + 1
sinon:
fin ← milieu - 1
retourner -1À chaque itération, on divise l'espace de recherche par 2
Nombre d'étapes nécessaires : log₂(n)
Calcul du milieu, comparaison, mise à jour des bornes : O(1)
log₂(n) × O(1) = O(log n)
La complexité temporelle de la recherche binaire est O(log n).
• Division par 2 : Chaque étape divise l'espace de recherche par 2 → O(log n)
• Condition préalable : Le tableau doit être trié
• Efficacité : Très efficace comparé à la recherche linéaire O(n)
Suite de Fibonacci : F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) pour n≥2.
fonction fibonacci(n):
si n ≤ 1:
retourner n
retourner fibonacci(n-1) + fibonacci(n-2)Pour fibonacci(n), on appelle fibonacci(n-1) et fibonacci(n-2)
Chaque appel génère 2 nouveaux appels, sauf pour les cas de base
Hauteur de l'arbre : n
Nombre approximatif de noeuds : 2^n
Cela donne une complexité exponentielle
fibonacci(k) est calculé plusieurs fois pour k < n
Cela rend l'algorithme très inefficace
La complexité temporelle de la version récursive de Fibonacci est O(2^n).
• Récursion sans mémoïsation : Peut conduire à des calculs redondants
• Complexité exponentielle : Très inefficace pour grandes valeurs de n
• Amélioration : Utiliser la programmation dynamique pour O(n)
Multiplication de matrices : Produit de deux matrices carrées de taille n×n.
fonction multiplierMatrices(A, B, n):
C ← matrice vide n×n
pour i de 0 à n-1:
pour j de 0 à n-1:
C[i][j] ← 0
pour k de 0 à n-1:
C[i][j] ← C[i][j] + A[i][k] * B[k][j]
retourner C3 boucles imbriquées, chacune exécutée n fois
Complexité : O(n) × O(n) × O(n) = O(n³)
Chaque élément C[i][j] nécessite n multiplications et additions
Total : n² éléments × n opérations = n³ opérations
Algorithme classique de multiplication de matrices : O(n³)
La complexité temporelle de la multiplication de matrices carrées est O(n³).
• Boucles imbriquées : Multiplier les complexités de chaque niveau
• Algorithmes avancés : Strassen propose O(n^2.807)
• Complexité cubique : Inefficace pour grandes matrices
- Top-down : Analyser le code ligne par ligne
- Bottom-up : Comprendre la structure de l'algorithme
- Théorème maître : Pour les récurrences de la forme T(n) = aT(n/b) + f(n)
- Arbre récursif : Pour visualiser les appels récursifs
- On néglige les constantes multiplicatives et les termes d'ordre inférieur
- Seul le terme dominant est conservé dans la notation O
- La complexité spatiale mesure l'espace mémoire utilisé
- Un algorithme polynomial est généralement préférable à un exponentiel
