Précédent Remonter Suivant

Chapitre 7  Introduction à la complexité des algorithmes

7.1  Complexité des algorithmes

La complexité (temporelle) d'un algorithme est le nombre d'opérations élémentaires (affectations, comparaisons, opérations arithmétiques) effectuées par un algorithme. Ce nombre s'exprime en fonction de la taille n des données. On s'intéresse au coût exact quand c'est possible, mais également au coût moyen (que se passe-t-il si on moyenne sur toutes les exécutions du programme sur des données de taille n), au cas le plus favorable, ou bien au cas le pire. On dit que la complexité de l'algorithme est O(f(n)) où f est d'habitude une combinaison de polynômes, logarithmes ou exponentielles. Ceci reprend la notation mathématique classique, et signifie que le nombre d'opérations effectuées est borné par cf(n), où c est une constante, lorsque n tend vers l'infini.

Considérer le comportement à l'infini de la complexité est justifié par le fait que les données des algorithmes sont de grande taille et qu'on se préoccupe surtout de la croissance de cette complexité en fonction de la taille des données. Une question systématique à se poser est: que devient le temps de calcul si on multiplie la taille des données par 2? De cette façon, on peut également comparer des algorithmes entre eux.

Les algorithmes usuels peuvent être classés en un certain nombre de grandes classes de complexité. La recherche de l'algorithme ayant la plus faible complexité, pour résoudre un problème donné, fait partie du travail régulier de l'informaticien. Il ne faut toutefois pas tomber dans certains excès, par exemple proposer un algorithme excessivement alambiqué, développant mille astuces et ayant une complexité en O(n1,99), alors qu'il existe un algorithme simple et clair de complexité O(n2). Surtout, si le gain de l'exposant de n s'accompagne d'une perte importante dans la constante multiplicative: passer d'une complexité de l'ordre de n2/2 à une complexité de 1010 n log n n'est pas vraiment une amélioration. Les critères de clarté et de simplicité doivent être considérés comme aussi importants que celui de l'efficacité dans la conception des algorithmes.

7.2  Calculs élémentaires de complexité

Donnons quelques règles simples concernant ces calculs. Tout d'abord, le coût d'une suite de deux instructions est la somme des deux coûts :
T(P; Q) = T(P) + T(Q).
Plus généralement, si l'on réalise une itération, on somme les différents coûts :
T(for(i = 0; i < n; i++) P(i); ) =
n-1
i=0
T(P(i)).

Si f et g sont deux fonctions positives réelles, on écrit
f = O(g)
si et seulement si le rapport f/g est borné à l'infini :
n0,    ∃ K,    ∀ nn0,    0 ≤ f(n) ≤ K g(n).
Autrement dit, f ne croît pas plus vite que g.

Autres notations : f = Θ(g) si f = O(g) et g = O(f).

Les règles de calcul simples sur les O sont les suivantes (n'oublions pas que nous travaillons sur des fonctions de coût, qui sont à valeur positive) : si f = O(g) et f' = O(g'), alors
f+f' = O(g+g'),    f f' = O(g g').
On montre également facilement que si f = O(nk) et h = ∑i=1n f(i), alors h = O(nk+1) (approximer la somme par une intégrale).

7.3  Quelques algorithmes sur les tableaux

7.3.1  Recherche du plus petit élément

Reprenons l'exemple suivant:
  static int plusPetit (int[] x){
      int k = 0, n = x.length;

      for(int i = 1; i < n; i++)
          // invariant : k est l'indice du plus petit
          // élément de x[0..i-1]
          if(x[i] < x[k])
              k = i;
      return k;
  }
Dans cette fonction, on exécute n-1 tests de comparaison. La complexité est donc n-1 = O(n).

7.3.2  Recherche dichotomique

Si t est un tableau d'entiers triés de taille n, on peut écrire une fonction qui cherche si un entier donné se trouve dans le tableau. Comme le tableau est trié, on peut procéder par dichotomie : cherchant à savoir si x est dans t[g..d[, on calcule m = (g+d)/2 et on compare x à t[m]. Si x=t[m], on a gagné, sinon on réessaie avec t[g..m[ si t[m] > x et dans t[m+1..d[ sinon. Voici la fonction Java correspondante:
  static int rechercheDichotomique(int[] t, int x){
      int m, g, d, cmp;

      g = 0; d = N-1;
      do{
          m = (g+d)/2;
          if(t[m] == x)
              return m;
          else if(t[m] < x)
              d = m-1;
          else
              g = m+1;
      } while(g <= d);
      return -1;
  }
Notons que l'on peut écrire cette fonction sous forme récursive :
  // recherche de x dans t[g..d[
  static int dichoRec(int[] t, int x, int g, int d){
      int m;

      if(g >= d) // l'intervalle est vide
          return -1;
      m = (g+d)/2;
      if(t[m] == x)
          return m;
      else if(t[m] > x)
          return dichoRec(t, x, g, m);
      else
          return dichoRec(t, x, m+1, d);
  }

  static int rechercheDicho(int[] t, int x){
      return dichoRec(t, x, 0, t.length);
  }
Le nombre maximal de comparaisons à effectuer pour un tableau de taille n est:
T(n) = 1 + T(n/2).
Pour résoudre cette récurrence, on écrit n = 2t, ce qui conduit à
T(2t) = T(2t-1)+1 = ⋯ = T(1)+t
d'où un coût en O(t) = O(logn).

On verra dans les chapitres suivants d'autres calculs de complexité, temporelle ou bien spatiale.

7.3.3  Recherche simultanée du maximum et du minimum

L'idée est de chercher simultanément ces deux valeurs, ce qui va nous permettre de diminuer le nombre de comparaisons nécessaires. La remarque de base est que étant donnés deux entiers a et b, on les classe facilement à l'aide d'une seule comparaison, comme programmé ici. La fonction retourne un tableau de deux entiers, dont le premier s'interprète comme une valeur minimale, le second comme une valeur maximale.
  // SORTIE: retourne un couple u = (x, y) avec 
  // x = min(a, b), y = max(a, b)
  static int[] comparerDeuxEntiers(int a, int b){
      int[] u = new int[2];

      if(a < b){
          u[0] = a; u[1] = b;
      }
      else{
          u[0] = b; u[1] = a;
      }
      return u;
  }
Une fois cela fait, on procède récursivement: on commence par chercher les couples min-max des deux moitiés, puis en les comparant entre elles, on trouve la réponse sur le tableau entier:
  // min-max pour t[g..d[
  static int[] minMaxAux(int[] t, int g, int d){
      int gd = d-g;

      if(gd == 1){
          // min-max pour t[g..g+1[ = t[g], t[g]
          int[] u = new int[2];

          u[0] = u[1] = t[g];
          return u;
      }
      else if(gd == 2)
          return comparerDeuxEntiers(t[g], t[g+1]);
      else{ // gd > 3
          int m = (g+d)/2;
          int[] tg = minMaxAux(t, g, m); // min-max de t[g..m[
          int[] td = minMaxAux(t, m, d); // min-max de t[m..d[
          int[] u = new int[2];

          if(tg[0] < td[0])
              u[0] = tg[0];
          else
              u[0] = td[0];
          if(tg[1] > td[1])
              u[1] = tg[1];
          else
              u[1] = td[1];
          return u;
      }
  }
Il ne reste plus qu'à écrire la fonction de lancement:
  static int[] minMax(int[] t){
      return minMaxAux(t, 0, t.length);
  }
Examinons ce qui se passe sur l'exemple
int[] t = {1, 4, 6, 8, 2, 3, 6, 0}.
On commence par chercher le couple min-max sur tg = {1, 4, 6, 8}, ce qui entraîne l'étude de tgg = {1, 4}, d'où ugg = (1, 4). De même, ugd = (6, 8). On compare 1 et 6, puis 4 et 8 pour finalement trouver ug = (1, 8). De même, on trouve ud = (0, 6), soit au final u = (0, 8).

Soit T(k) le nombre de comparaisons nécessaires pour n=2k. On a T(1) = 1 et T(2) = 2 T(1)+2. Plus généralement, T(k) = 2 T(k-1)+2. D'où
T(k) = 22 T(k-2)+22+2 = ⋯ = 2u T(k-u)+2u+2u-1+⋯+2
soit
T(k) = 2k-1 T(1)+2k-1+⋯+2 = 2k-1+2k-2 = n/2+n-2 = 3 n/2-2.

7.4  Exponentielle binaire

Cet exemple va nous permettre de montrer que dans certains cas, on peut calculer la complexité dans le meilleur cas ou dans le pire cas, ainsi que calculer le comportement de l'algorithme en moyenne.

Supposons que l'on doive calculer xn avec x appartenant à un groupe quelconque. On peut calculer cette quantité à l'aide de n-1 multiplications par x, mais on peut faire mieux en utilisant les formules suivantes:



Par exemple, on calcule
x11 = x (x5)2 = x (x (x2)2)2,
ce qui coûte 5 multiplications (en fait 3 carrés et 2 multiplications).

La fonction évaluant xn avec x de type long correspondant aux formules précédentes est:
static long Exp(long x, int n){
    if(n == 0) return 1;
    else{
        if((n%2) == 0){
            long y = Exp(x, n/2);
            return y * y;
        }
        else{
            long y = Exp(x, n/2);
            return x * y * y;
        }
    }
}

Soit E(n) le nombre de multiplications réalisées pour calculer xn. En traduisant directement l'algorithme, on trouve que:



Écrivons n > 0 en base 2, soit n = 2t-1+∑i=0t-2 bi 2i = bt-1 bt-2b0 = 2t-1 + n' avec t ≥ 1, bi ∈ {0, 1}. On récrit donc:

On pose ν(n') = ∑i=0t-2 bi. On peut se demander quel est l'intervalle de variation de ν(n'). Si n = 2t-1, alors n'=0 et ν(n')=0, et c'est donc le cas le plus favorable de l'algorithme. À l'opposé, si n = 2t-1 = 2t-1+2t-2+⋯ +1, ν(n')=t-1 et c'est le cas le pire.

Reste à déterminer le cas moyen, ce qui conduit à estimer la quantité:



On peut récrire cela comme:

où les sommes sont toutes indexées par les 2t-1 t-1-uplets formés par les (b0, b1, …, bt-2) possibles dans {0, 1}t-1. Toutes ces sommes sont égales par symétrie, d'où: Cette dernière somme ne contient que les valeurs pour b0=1 et les bi restant prenant toutes les valeurs possibles, d'où finalement: Autrement dit, un entier de t-1 bits a en moyenne (t-1)/2 chiffres binaires égaux à 1.

En conclusion, l'algorithme a un coût moyen
E
(n) = t+(t-1)/2 =
3
2
t + c
avec t = ⌊ log2 n ⌋ et c une constante.
Précédent Remonter Suivant