Complexité constante O(1) : Le temps d'exécution ne dépend pas de la taille des données.
Opérations élémentaires : Accès à un tableau par index, opérations arithmétiques.
- Identifier les opérations élémentaires (affectation, comparaison, calcul)
- Compter le nombre d'opérations en fonction de la taille d'entrée n
- Identifier le terme dominant (celui qui croît le plus rapidement)
- Exprimer la complexité en notation O en ignorant les constantes
Instruction : x = 5
Cette instruction réalise une seule opération d'affectation
Nombre d'opérations : 1 (indépendant de toute taille d'entrée)
T(n) = 1 → O(1) (constante)
L'opération x = 5 a une complexité constante O(1) car elle s'exécute en un temps fixe.
• Complexité constante : Temps d'exécution indépendant de la taille des données
• Opérations élémentaires : Affectations, calculs arithmétiques simples
• Accès direct : Accès à un tableau par index est en O(1)
Complexité linéaire O(n) : Le temps d'exécution est proportionnel à la taille des données.
Caractéristique : Une boucle qui parcourt n éléments exécutant une opération O(1).
Algorithme de somme d'un tableau de n éléments
somme = 0
pour i de 0 à n-1:
somme = somme + tableau[i]
retourner somme
Initialisation : 1 opération (O(1))
Boucle : n itérations
Par itération : 1 addition + 1 accès tableau + 1 affectation = 3 opérations O(1)
Total : 1 + n×3 = 3n + 1 opérations
T(n) = 3n + 1 → O(n) (terme dominant : n)
| Taille (n) | Opérations | Temps relatif |
|---|---|---|
| 10 | 31 | 1× |
| 100 | 301 | 10× |
| 1000 | 3001 | 100× |
| 10000 | 30001 | 1000× |
L'algorithme de somme d'un tableau a une complexité linéaire O(n).
• Complexité linéaire : Une boucle simple parcourant n éléments
• Terme dominant : Dans 3n+1, c'est n qui domine pour les grandes valeurs
• Proportionnalité : Le temps double quand la taille double
Complexité quadratique O(n²) : Le temps d'exécution est proportionnel au carré de la taille des données.
Caractéristique : Boucles imbriquées où chaque boucle parcourt n éléments.
Algorithme de tri par sélection
pour i de 0 à n-2:
min = i
pour j de i+1 à n-1:
si tableau[j] < tableau[min]:
min = j
échanger tableau[i] et tableau[min]
Boucle extérieure : (n-1) itérations
Pour chaque i, boucle intérieure : (n-1-i) itérations
Total d'itérations de la boucle intérieure : Σ(i=0 à n-2)(n-1-i) = Σ(k=1 à n-1)k = (n-1)n/2
T(n) = (n-1)n/2 = (n²-n)/2 = n²/2 - n/2 → O(n²) (terme dominant : n²)
Pour n=10 : (10-1)×10/2 = 45 comparaisons
Pour n=100 : (100-1)×100/2 = 4950 comparaisons
Quand n est multiplié par 10, le nombre d'opérations est multiplié par ~100
| Taille (n) | Opérations | Temps relatif |
|---|---|---|
| 10 | 45 | 1× |
| 20 | 190 | 4.2× |
| 50 | 1225 | 27.2× |
| 100 | 4950 | 110× |
L'algorithme de tri par sélection a une complexité quadratique O(n²).
• Complexité quadratique : Boucles imbriquées parcourant n éléments
• Croissance rapide : Le temps augmente exponentiellement avec la taille
• Optimisation : Chercher des algorithmes plus efficaces pour de grandes données
Comparaison d'algorithmes : Analyse des performances selon la taille des données.
Hiérarchie : O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
O(1) : Constante (meilleure)
O(log n) : Logarithmique
O(n) : Linéaire
O(n log n) : Linéarithmique
O(n²) : Quadratique
O(2ⁿ) : Exponentielle (pire)
Pour n = 1000 :
O(1) = 1 opération
O(log n) ≈ 10 opérations
O(n) = 1000 opérations
O(n²) = 1,000,000 opérations
Un algorithme O(n²) devient impraticable pour de grandes valeurs de n
Un algorithme O(n) est acceptable pour des données de taille modérée
Un algorithme O(1) est optimal en termes de performance
• Taille attendue des données
• Contraintes de temps réel
• Complexité de mise en œuvre
• Mémoire disponible
| Complexité | n=10 | n=100 | n=1000 | n=10000 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 |
| O(log n) | ~3 | ~7 | ~10 | ~13 |
| O(n) | 10 | 100 | 1000 | 10000 |
| O(n log n) | ~30 | ~700 | ~10000 | ~130000 |
| O(n²) | 100 | 10000 | 1000000 | 100000000 |
La hiérarchie des complexités détermine les performances relatives des algorithmes.
• Hiérarchie : Comparer les ordres de grandeur des complexités
• Impact : Une différence de complexité peut entraîner des gains énormes
• Choix : Équilibrer performance, simplicité et besoins spécifiques
Algorithmes classiques : Analyse de la complexité de structures et algorithmes courants.
Pratique : Comprendre la performance des algorithmes utilisés quotidiennement.
Complexité : O(n)
Algorithme : Parcourir le tableau élément par élément
Applicable à : Tableaux non triés
Complexité : O(log n)
Algorithme : Diviser l'espace de recherche par 2 à chaque étape
Condition : Le tableau doit être trié
Complexité : O(n²) dans le pire cas
Algorithme : Insérer chaque élément à sa place dans la partie triée
Avantage : Efficace pour de petites tailles
Complexité : O(n log n)
Algorithme : Diviser pour régner - diviser, trier, fusionner
Avantage : Garantie O(n log n) dans tous les cas
| Algorithme | Type | Meilleur cas | Pire cas | Utilisation |
|---|---|---|---|---|
| Recherche linéaire | Recherche | O(1) | O(n) | Tableau non trié |
| Recherche dichotomique | Recherche | O(1) | O(log n) | Tableau trié |
| Tri par insertion | Tri | O(n) | O(n²) | Petites données |
| Tri fusion | Tri | O(n log n) | O(n log n) | Grandes données |
| Tri rapide | Tri | O(n log n) | O(n²) | Général |
La connaissance de la complexité permet de choisir le bon algorithme pour chaque situation.
• Contexte : Choisir l'algorithme en fonction des contraintes
• Structure : La complexité dépend souvent de la structure de données
• Compromis : Équilibre entre complexité, lisibilité et besoins spécifiques
- O(1) - Constante : Temps fixe, indépendant de la taille d'entrée
- O(log n) - Logarithmique : Temps proportionnel au logarithme de la taille
- O(n) - Linéaire : Temps proportionnel à la taille d'entrée
- O(n log n) - Linéarithmique : Fréquent dans les algorithmes de tri efficaces
- O(n²) - Quadratique : Courant dans les algorithmes avec boucles imbriquées
- O(2ⁿ) - Exponentielle : Algorithmes récursifs sans optimisation
- La complexité mesure le comportement asymptotique pour des grandes tailles d'entrée
- Les constantes multiplicatives sont ignorées dans la notation O
- Le terme dominant détermine la complexité globale
- Les algorithmes avec des complexités inférieures sont préférables
- • La complexité algorithmique mesure l'efficacité des algorithmes en fonction de la taille des données
- • La notation O exprime les bornes supérieures du comportement asymptotique
- • La hiérarchie des complexités détermine la performance relative des algorithmes
- • Le choix de l'algorithme dépend du contexte, des contraintes et des tailles de données
- • Comprendre la complexité permet d'anticiper les performances et d'optimiser les programmes
