Chapitre 4 : Notion de Complexité des Algorithmes

Introduction et Objectifs

Objectif général : Bien comprendre les notions de complexité des algorithmes.

Objectifs spécifiques : Être capable de :

• Définir les notions de complexité.
• Connaître les types de complexité.
• Déterminer la complexité des algorithmes informatiques.

L’objectif de ce chapitre est de permettre d’évaluer les performances d’un algorithme (en temps d’exécution ou en espace mémoire) pour faire des choix d’optimisation.

I. Définition des notions de complexité

• La complexité en espace : correspond à l’espace mémoire (nombre d’octets ou de variables) nécessaire à l’exécution sur une donnée de taille N.
• La complexité en temps : correspond au temps d’exécution (nombre d’opérations élémentaires) de l’algorithme en fonction de la taille N des données d’entrée.

II. Détermination de la complexité (Exemples)

a. Cas N° 1 : Algorithme qui permute deux nombres

Solution 1 : Classique avec variable intermédiaire

entier x, y, z;
z ← x;
x ← y;
y ← z;

Analyse : Utilisation de 3 variables (donc 3 espaces mémoire). L’algorithme effectue 3 affectations. Sa complexité temporelle est constante d’ordre 3, notée O(3).

Solution 2 : Mathématique sans variable supplémentaire

entier x, y;
x ← y - x;
y ← y - x;
x ← y + x;

Analyse : Utilisation de 2 variables. Cependant, en plus de 3 affectations, on a 3 opérations arithmétiques (additions/soustractions). Sa complexité temporelle est constante d’ordre 6, notée O(6).

Conclusion : L’algorithme le plus performant en terme de temps d’exécution est la solution 1, malgré une légère surconsommation spatiale.

b. Cas N°2 : Calcul de la factorielle

Fonction factorielle (entier n) : entier
  Var i, resultat : entier ;
Début
  resultat ← 1;
  pour (i allant de 2 à n) faire
    resultat ← resultat * i;
  finpour
  retourne resultat;
Fin

Analyse : La complexité est de l’ordre O(t + (n-1)[k+p]), ce qui est asymptotiquement équivalent à O(n), c’est-à-dire une complexité linéaire.

III. Types de complexité

Lors de l’analyse asymptotique (Grand O), on distingue plusieurs types de complexité :

• O(1) : complexité constante. Pas d’augmentation du temps d’exécution quand la taille des données croît.
• O(n) : complexité linéaire. Augmentation proportionnelle de la taille. (ex: parcours d’un tableau à une dimension).
• O(n^2) : complexité quadratique. Le temps d’exécution est mis au carré. (ex: tri à bulles sur pire cas, deux boucles imbriquées). Plus généralement O(n^i) pour une complexité polynomiale avec i boucles imbriquées.
• O(2^n) : complexité exponentielle. L’augmentation devient très rapide (ex: tours de Hanoï).
• O(n!) : complexité factorielle. Temps d’exécution le plus critique (ex: génération de toutes les permutations).

IV. Travaux dirigés

• Exercice 1 : Déterminer la complexité d’une fonction de recherche itérative qui renvoie la position d’un client dans un tableau donné (ex: RecherchePositionClient).
• Exercice 2 : Évaluer et déterminer la notation O() des portions de code suivantes :
  • Cas 1 : 2 boucles imbriquées pour itérant de 1 à n.
  • Cas 2 : 2 boucles imbriquées s’exécutant sur des plages spécifiques limitées par des constantes.
  • Cas 3 : 3 boucles imbriquées pour itérant de 1 à n.