Calculs de complexité d'algorithmes

Ce document présente les notions fondamentales sur le calcul de la complexité des algorithmes, destiné aux étudiants en informatique ou mathématiques souhaitant comprendre comment évaluer l'efficacité des algorithmes en termes de temps et d'espace. Il aborde les notations asymptotiques, les règles de calcul de complexité, des exemples concrets, ainsi que des méthodes de résolution d'équations de récurrence liées à la programmation récursive.

Complexité des algorithmes

Un algorithme transforme une donnée d'entrée en un résultat. La taille de la donnée est notée par un entier n.

On distingue :

• Complexité temporelle : fonction de n mesurant le temps de calcul nécessaire pour une donnée de taille n.
• Complexité en mémoire : fonction de n mesurant la place mémoire utilisée pour le calcul.

Complexité temporelle

On peut mesurer la complexité temporelle :

• Dans le pire des cas : donne une borne supérieure sur le temps de calcul pour toutes les données de taille n.
• En moyenne : moyenne des temps de calcul pour toutes les données de taille n.

Le temps de calcul n'est pas mesuré directement car il dépend de la machine. On compte plutôt le nombre d'opérations élémentaires (additions, multiplications, etc.). On considère uniquement le terme dominant de cette estimation.

Notations asymptotiques

Soient f et g deux fonctions de n.

• f = O(g) signifie que f est dominée par g, c’est-à-dire qu’il existe n0 et c > 0 tels que pour tout n ≥ n0, f(n) ≤ c g(n).
• f = Θ(g) signifie que f est du même ordre de grandeur que g, c’est-à-dire f = O(g) et g = O(f).
• f = o(g) signifie que f est négligeable devant g, c’est-à-dire que f(n)/g(n) tend vers 0 quand n tend vers l’infini.
• f est équivalente à g signifie que f(n)/g(n) tend vers 1 quand n tend vers l’infini.

Ces notions sont indépendantes des constantes multiplicatives non nulles, sauf pour l'équivalence.

Exemple

Pour tout entier k, on a :

∑(i=0 à n) i^k = Θ(n^(k+1))

Règles de calcul de complexité

Composition séquentielle

Si I1 a une complexité Θ(f1(n)) et I2 une complexité Θ(f2(n)), alors la complexité de l'exécution séquentielle :

I1;
I2;

est :

Θ(max(f1(n), f2(n)))

Conditionnelle if-else

Si l’évaluation de la condition C est en Θ(f(n)), I1 en Θ(f1(n)) et I2 en Θ(f2(n)), alors :

La complexité de :

if (C) I1 else I2

est en :

O(max(f(n), f1(n), f2(n)))

Boucle for

Si I1 a une complexité Θ(f1(n)) et ne modifie pas les variables de contrôle, alors la boucle :

for (int i=0; i < n; i++) {
  I1
}

a une complexité :

Θ(n * f1(n))

Boucle while

Si l’évaluation de la condition C est en Θ(f(n)), I en Θ(f1(n)) et la boucle s’exécute Θ(g(n)) fois :

while (C) {
  I
}

La complexité est :

Θ(g(n) * max(f(n), f1(n)))

Exemple de complexité d’une boucle imbriquée

for (int i=0; i < n; i++) {
  for (int j=i; j < n; j++) {
    for (int k=0; k < j; k++) {
      I1; // Θ(1)
    }
  }
}

Complexité :

Θ(∑_{i=0}^{n-1} ∑_{j=i}^{n-1} j) = Θ(∑_{i=0}^{n-1} (n^2)) = Θ(n^3)

Composition de méthodes

Si methode1 a une complexité O(f1(taille1(o1))) et methode2 a une complexité O(f2(taille2(o2))) et que methode2 renvoie un objet de Classe1, alors :

La complexité de :

methode1(methode2(o2))

est :

O(max(f2(taille2(o2)), f1(taille1(methode2(o2)))))

Exemples d’analyse de complexité

Conversion d’un nombre en base b vers la base 10

Méthode "convertionDirecte" :

public int convertionDirecte(int[] a, int b) {
  int résultat = a[0];
  int auxiliaire;
  for (int rang = 1; rang < a.length; rang++) {
    if (a[rang] != 0) {
      auxiliaire = a[rang];
      for (int indice = 0; indice < rang; indice++) {
        auxiliaire = auxiliaire * b;
      }
      résultat = résultat + auxiliaire;
    }
  }
  return résultat;
}

Complexité :

Le double for imbriqué donne Θ(n^2).

Méthode "convertionDirecteV2"

On mémorise dans une variable monome brang la puissance de b pour éviter la boucle interne :

public int convertionDirecteV2(int[] a, int b) {
  int résultat = a[0];
  int monome = 1;
  for (int rang = 1; rang < a.length; rang++) {
    monome = monome * b;
    if (a[rang] != 0) {
      résultat = résultat + a[rang] * monome;
    }
  }
  return résultat;
}

Complexité :

La boucle simple donne une complexité Θ(n).

Méthode de Horner

public int horner(int[] a, int b) {
  int n = a.length;
  int résultat = a[n-1];
  for (int rang = n-2; rang >= 0; rang--) {
    résultat = b * résultat + a[rang];
  }
  return résultat;
}

Complexité :

La boucle unique donne une complexité Θ(n).

Élévation à la puissance

Méthode naïve :

public int puissance(int n, int a) {
  int résultat = a;
  for (int i = 1; i < n; i++) {
    résultat = résultat * a;
  }
  return résultat;
}

Complexité :

Θ(n) multiplications.

Méthode rapide (exponentiation par squaring)

public int puissance(int n, int a) {
  int aux = n;
  int puissanceDea = a;
  int résultat = 1;
  while (aux != 0) {
    if (aux % 2 == 1) {
      résultat = résultat * puissanceDea;
    }
    aux = aux / 2;
    puissanceDea = puissanceDea * puissanceDea;
  }
  return résultat;
}

Complexité :

Θ(log n) multiplications.

Programmation récursive et équations de récurrence

La complexité des algorithmes récursifs est souvent exprimée par des équations de récurrence.

Exemple : Factorielle

int factorial(int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n-1);
  }
}

Nombre de multiplications c(n) :

c(n) = c(n-1) + 1, avec c(1) = 0

Donc c(n) = Θ(n).

Recherche du maximum dans un tableau

Algorithme récursif :

• Si n=1, retourner l’élément unique.
• Sinon, chercher récursivement le max des n-1 premiers éléments, puis comparer avec le dernier.

Complexité :

c(n) = c(n-1) + 1 avec c(1) = 0, donc c(n) = Θ(n).

Tours de Hanoi

public static void moveTowers(int n, char from, char inter, char to) {
  if (n == 1) {
    moveDisk(1, from, to);
  } else {
    moveTowers(n-1, from, to, inter);
    moveDisk(n, from, to);
    moveTowers(n-1, inter, from, to);
  }
}

Nombre de déplacements c(n) :

c(n) = 2 c(n-1) + 1

Solution :

c(n) = Θ(2^n)

Suite de Fibonacci

Définie par :

F(n) = F(n-1) + F(n-2) avec F(0) = 0, F(1) = 1

Exemple de calcul récursif :

public int fibonacci(int n) {
  if (n == 0) return 0;
  else if (n == 1) return 1;
  else return fibonacci(n-1) + fibonacci(n-2);
}

Complexité :

c(n) = c(n-1) + c(n-2) + 1, ce qui est exponentiel.

Version itérative améliorée

public int fibonacci(int n) {
  int fiMoins2 = 0;
  int fiMoins1 = 1;
  int fi = 1;
  for (int i = 3; i <= n; i++) {
    fi = fiMoins2 + fiMoins1;
    fiMoins2 = fiMoins1;
    fiMoins1 = fi;
  }
  if (n == 0) return 0;
  else return fi;
}

Complexité :

Θ(n) (linéaire).

Version rapide (complexité logarithmique)

Utilise la décomposition de n en base 2 et des formules matricielles pour calculer F(n) en Θ(log n).

Solutions de type diviser pour régner

Pour un problème de taille n, on le divise en a sous-problèmes de taille n/b, chacun résolu récursivement, avec une phase de division et de combinaison de complexité f(n).

L'équation de récurrence est :

T(1) = constante

T(n) = a T(n/b) + f(n)

Théorème

• Si f(n) = O(n^(log_b a - ε)) pour ε > 0, alors T(n) = Θ(n^(log_b a)).
• Si f(n) = Θ(n^(log_b a)), alors T(n) = Θ(n^(log_b a) log n).
• Si f(n) = Ω(n^(log_b a + ε)) pour ε > 0 et si a f(n/b) ≤ c f(n) pour c < 1, alors T(n) = Θ(f(n)).

Exemple : Recherche dichotomique du maximum

Relation :

c(n) = 2 c(n/2) + 1

Complexité :

Θ(n)

Exemple : Tri dichotomique

Relation :

c(n) = 2 c(n/2) + n

Complexité :

Θ(n log n)

Multiplication récursive de grands nombres

Soient U et V deux nombres de 2n chiffres en base B, écrits :

U = U1 B^n + U2, V = V1 B^n + V2

Méthode naïve

Nombre de multiplications élémentaires :

Θ(n^2)

Méthode récursive classique

On calcule :

(U1 B^n + U2)(V1 B^n + V2) = U1 V1 B^{2n} + (U1 V2 + U2 V1) B^n + U2 V2

Ce qui donne 4 multiplications de nombres de taille n, plus additions et décalages en Θ(n).

Relation de récurrence :

T(2n) = 4 T(n) + Θ(n)

Complexité :

Θ(n^{log_2 4}) = Θ(n^2)

Méthode de Karatsuba

On utilise :

(U1 B^n + U2)(V1 B^n + V2) = U1 V1 B^{2n} + ((U1 - U2)(V2 - V1) + U2 V2 + U1 V1) B^n + U2 V2

Ce qui ramène la multiplication à 3 multiplications de taille n, plus additions et décalages en Θ(n).

Relation :

T(2n) = 3 T(n) + Θ(n)

Complexité :

Θ(n^{log_2 3}) ≈ Θ(n^{1.585})

Fusion de plusieurs listes triées

Soient p listes triées de longueur n.

Méthode itérative

public static Liste fusionMultiple(Liste[] mesListes) {
  Liste L = mesListes[0];
  for (int i = 1; i < mesListes.length; i++) {
    L = Liste.fusion(L, mesListes[i]);
  }
  return L;
}

Complexité :

Θ(p n p) = Θ(n p^2)

Méthode récursive (multifusion)

• Si p = 2, utiliser fusion.
• Sinon, multifusionner récursivement les p/2 premières listes, puis les p/2 dernières, puis fusionner les deux résultats.

Relation de récurrence :

c(n, p) = 2 c(n, p/2) + Θ(n p)

En posant d(n, p) = c(n, p)/n, on montre que d(n, p) ne dépend pas de n et que :

f(p) = 2 f(p/2) + p

Solution :

f(p) = Θ(p log p)

Donc :

c(n, p) = Θ(n p log p)

Exemple d'algorithme récursif avec complexité non triviale

public void T(int debut, int fin) {
  int n = fin - debut + 1;
  if (n > 1) {
    if (n == 2) {
      if (table.elementAt(debut) > table.elementAt(fin)) {
        table.echanger(debut, fin);
      }
    } else {
      T(debut, debut + n/b);
      T(fin - n/b, fin);
      T(debut, debut + n/b);
    }
  }
}

Relation de récurrence :

T(n) = 3 T(n/b) + O(1)

Pour b = 3/2, la complexité peut être analysée via le théorème du maître.

Glossaire des termes clés

• Complexité temporelle : mesure du temps de calcul en fonction de la taille de la donnée.
• Complexité en mémoire : mesure de la mémoire utilisée en fonction de la taille de la donnée.
• Notation O (grand O) : borne supérieure asymptotique d’une fonction.
• Notation Θ (thêta) : ordre de grandeur exact asymptotique d’une fonction.
• Notation o (petit o) : fonction négligeable devant une autre asymptotiquement.
• Terme dominant : terme qui croît le plus rapidement dans une fonction.
• Équation de récurrence : relation définissant une fonction en fonction de ses valeurs précédentes.
• Diviser pour régner : technique algorithmique divisant un problème en sous-problèmes plus petits.
• Exponentiation rapide : méthode d’élévation à la puissance en temps logarithmique.
• Programme récursif : programme qui s’appelle lui-même pour résoudre un problème.

Points clés à retenir

• La complexité s’exprime en fonction de la taille de la donnée, notée n.
• Les notations asymptotiques O, Θ, o permettent de comparer la croissance des fonctions de complexité.
• Le terme dominant est celui qui détermine la complexité asymptotique.
• Les règles de calcul permettent d’évaluer la complexité de structures séquentielles, conditionnelles et itératives.
• Les équations de récurrence modélisent la complexité des algorithmes récursifs et se résolvent par des méthodes mathématiques.
• La programmation récursive naïve peut entraîner une complexité exponentielle, comme pour Fibonacci.
• Des versions itératives ou optimisées réduisent souvent la complexité, par exemple Fibonacci en Θ(n) ou Θ(log n).
• Le théorème du maître donne un cadre pour résoudre les équations de récurrence de type diviser pour régner.
• Les algorithmes récursifs peuvent être optimisés en réduisant le nombre d’appels récursifs, comme dans la multiplication de Karatsuba.
• La compréhension des complexités permet de choisir ou concevoir des algorithmes efficaces pour des problèmes donnés.