Définitions

La complexité d'un pseudo-code est une mesure associée au pseudo-code. Elle peut mesurer 2 grandeurs physique lors de l'exécution d'un algorithme :

• complexité en temps : le nombre d'instructions effectuées pendant son exécution
• complexité en espace : le nombre de cases mémoires maximales utilisées pendant son exécution.

Par défaut, la complexité utilisée est celle en temps :

Par exemple le pseudo-code suivant :

x ← 30
si ((x > 12) ET (x < 36)):
    z ← "entre 13 et 35"

• première ligne : 2 instructions
  1. Création de l'entier valant 30 : 1 instruction
  2. on affecte l'entier à x : 1 instruction
• deuxième ligne : 8 instructions
  1. faire x > 12. Pour cela :
     • on crée l'entier valant 12 : 1 instruction
     • on récupère la valeur de x : 1 instruction
     • on effectue la comparaison : 1 instruction
  2. faire x < 36. Pour cela :
     • on crée l'entier valant 36 : 1 instruction
     • on récupère la valeur de x : 1 instruction
     • on effectue la comparaison : 1 instruction
  3. faire l'instruction AND : 1 instruction
  4. faire le si : 1 instruction
• troisième ligne : 2 instructions
  1. on crée la chaîne : 1 instruction
  2. puis affecte le résultat : 1 instruction

Un nombre total d'instructions de 12 pour ces trois lignes de pseudo-code.

Complexité des appels de fonctions

Si l'on devait à chaque pseudo-code redéfinir tout les algorithmes qu'on utilise ce serait vraiment fastidieux. On utilise souvent des fonctions non basiques (comme l'affichage à l'écran qu'on a déjà vu) ou des structures plus élaborées (les listes par exemples qui sont des extensions des tableaux). Il faudra cependant toujours connaître les complexités de ce qu'on utilise.

Prenons par exemple le code suivant et comptons les instructions utilisées au cours de son exécution :

fonction recherche(t: [entier], x: entier) → booléen:
    pour chaque e de t:
        si e == x:
            rendre Vrai
    rendre Faux

t ← [1, 2, 6]
trouve ← recherche(t, 6)
affiche à l'écran trouve

1. exécution de la ligne 7 : 8 instructions
   • création d'un tableau : 1 instruction
   • création de 3 entiers : 3 instructions
   • affectation des 3 entiers aux indices du tableau : 3 instructions
   • affectation du tableau à une variable : 1 instruction
2. exécution de la ligne 8 :
   1. exécution de la fonction recherche (ligne à ligne) :
      1. exécution de la ligne 1 : affectation des paramètres
         1. trouver les objets à mettre en paramètres :
            • pour le premier paramètre il faut trouver l'objet associé à t : 1 instruction
            • pour le second paramètre, l'objet est à créer : 1 instruction
         2. affecter les paramètres aux variables de la fonction :
            • affectation du premier paramètre à la variable locale t : 1 instruction
            • affectation du second paramètre à la variable locale x : 1 instruction
      2. exécution de la ligne 2 (3 fois) : trouver l'objet du tableau puis l'affecter à e : 2 instructions
      3. exécution de la ligne 3 (3 fois) : un test
         • on trouve les objets associées à t et e : 2 instructions
         • on teste l'égalité : 1 instruction
         • on fait le si : 1 instruction
      4. exécution de la ligne 4 (1 fois) : on arrive à cette ligne à la troisième itération : 2 instructions (une pour créer le booléen, l'autre pour le rendre)
   2. affection de la variable trouve
3. afficher quelque chose à l'écran :
   • 1 instruction pour trouver l'objet à afficher
   • 1 instruction pour trouver l'afficher

Au total on eu besoin de $8+\underbracket{(4 + 3 \cdot (4+4) + 2)}_{\mbox{recherche(t, 6)}} + 1 + 2$ instructions c'est à dire $41$ instructions.

Complexité des accès à un tableau ?

Combien d'instructions nécessite la création et l'accès à un tableau ?

On considérera en algorithmie que tous les accès à un élément donné d'un tableau nécessite 1 instruction. Ainsi :

• créer un tableau de taille $n$ nécessite 1 instruction
• accéder à un indice donnée en lecture nécessite 1 instruction
• accéder à un indice donnée pour une affectation nécessite 1 instruction

De là l'instruction :

• créer un tableau de taille 42 nécessite 1 instruction
• créer un tableau de taille $2^{42} nécessite 1 instruction
• F ← un tableau de taille 42 nécessite 2 instructions, une pour la création, la seconde pour l'affectation
• afficher à l'écran F[3] nécessite 2 instructions, une pour retrouver l'objet associé à F[3], l'autre pour l'afficher
• F[3] ← 42 nécessite 2 instructions, une pour créer l'entier 42, l'autre pour l'affecter
• F[i] ← 42 nécessite 3 instructions, une pour créer l'entier 42, une pour trouver l'objet associé à i (ce n'est pas une constante) l'autre pour l'affecter
• F[i-1] ← 42 nécessite 5 instructions, une pour créer l'entier 42, une pour trouver l'objet associé à i, une pour créer l'entier 1, une pour l'addition et la dernière pour l'affectation.

Complexité d'un algorithme

Le pseudo-code suivant, qui calcule la dixième valeur de la suite de Fibonacci a une complexité $C = 144$ :

F ← un tableau de 10 entiers
F[0] ← 1
F[1] ← 1

i ← 2
tant que i ≤ 9 :
  F[i] ← F[i - 1] + F[i - 2]
  i ← i + 1

rendre F[9]

Mais souvent la complexité dépend des paramètres du programme, comme par exemple le pseudo-code suivant qui rend la $n$ème valeur de la suite de Fibonacci où $n$ est le paramètre de l'algorithme :

algorithme fibonacci(n: entier) → entier:
  F ← un tableau de n entiers
  F[0] ← 1
  F[1] ← 1

  i ← 2
  tant que i < n :
    F[i] ← F[i - 1] + F[i - 2]    
    i ← i + 1

  rendre F[n-1]

Le nombre de fois où l'on rentre dans la boucle va dépendre de l'entrée et on a maintenant une complexité de $C(n) = 17\cdot n-20$ qui dépend de la valeur du paramètre d'entrée.

Enfin, en règle générale, la complexité dépend trop profondément de la nature même de ses entrées et empêche d'en tirer une allure générale. Par exemple l'algorithme suivant qui cherche si une valeur v est dans un tableau t :

algorithme recherche(t: [entier], x: entier) → booléen:
    pour chaque e de t:
        si e == x:
            rendre Vrai
    rendre Faux

La complexité de cet algorithme va dépendre de l'endroit où se trouve la valeur dans le tableau. Si l'on utilise la taille $n$ du tableau comme paramètre de complexité, sa complexité ira de 10 lorsque la valeur est le premier élément du tableau (les deux affectations des paramètres ; trouver t[0] puis l'affecter à e ; deux lectures, une opération booléenne et un test ; une création d'objet puis un retour) à $6n + 4$ si la valeur n'est pas dans le tableau (les deux affectations des paramètres ; $2n$ instruction de l'affectation de la boucle pour chaque ; $2n$ lectures, $n$ opérations booléennes et $n$ tests ; une création d'objet puis un retour). La complexité de l'algorithme est alors $C(i) = 6i + 4$ où $i$ est la position de la valeur dans le tableau.

Lorsque l'on utilise un algorithme on a jamais beaucoup de connaissances a priori sur ses entrées. Pour l'algorithme rechercher on sait que l'on a un entier et un tableau en paramètre mais pas la natures des entiers contenus dans le tableau. Avoir une complexité qui dépend des valeurs contenues dans le tableau est donc inutile en pratique. Il serait pus intéressant de connaître la complexité de l'algorithme pour un tableau d'une taille donnée. Dans ce cas là on calculera la complexité maximale pour tous les tableaux de même taille.

Connaissances minimales sur les entrées

Les connaissances minimales que l'on possède sur les données sont leurs tailles de stockage en mémoire.

Dans la partie pseudo-code on a considéré deux types de données :

• les types simples que sont les nombres et les caractères qui sont stockable sur 1 case mémoire
• les tableaux dont la taille est la somme des tailles de leurs éléments

Complexité algorithmique

En prenant en compte les connaissances minimales que l'on a sur les entrées d'un algorithme, sa complexité est définie comme suit :

En utilisant la définition ci-dessus, la complexité de l'algorithme recherche vaut $6N+4$.

Comme rien n'est jamais simple, il existe des cas où la connaissance de la taille ne done pas un critère pertinent pour établir une complexité. C'est souvent le cas lorsque les paramètres de l'algorithmes sont de taille fixe, comme pour la fonction fibonacci(n), la taille de stockage d'un entier étant de 1 case mémoire.

Si l'on avait calculé la complexité en regroupant les entrées par taille, on aurait eu qu'une seule classe d'entrée et la complexité aurait été infinie... Il a donc fallu supposer que l'on connaissait la valeur de l'entrée pour calculer une complexité finie.

Il n'y a pas de règle immuable dans le choix des connaissances que l'on s'accorde sur les paramètres, mais ne vous inquiétez pas, cela ressortira immédiatement du calcul. En revanche, comme la nature du paramètre peut changer :

Autres types de complexités

Lorsque l'on parle de complexité d'un algorithme ce sera toujours en utilisant la définition précédente. Il existe cependant d'autres types de complexité que l'on pourra utiliser.

Complexité min

Lorsqu'à paramètre fixé le nombre d'instructions varie selon les paramètres utilisé (l'algorithme recherche par exemple), la complexité prend le maximum ($6N+4$ où $N$ est la la taille du tableau en entrée pour l'algorithme recherche) mais il peut être utile de connaître le minimum ($10$ pour l'algorithme recherche, indépendant de la taille du tableau en entrée) pour voir la variation de ce nombre en fonction des entrées.

Complexité en temps

Lorsqu'un algorithme est codé, on peut l'exécuter et mesurer son temps d'exécution. On peut alors définir la complexité en temps d'exécution d'un code :

Si chaque instruction élémentaire prend le même temps à être effectuée sur une machine (ou que l'on borne le tout par l'instruction élémentaire la plus gourmande), la complexité d'un pseudo-code nous donne un nombre proportionnel au temps qu'il mettra à s'exécuter :

Si l'on connaît le jeu de paramètres d'entrée réalisant la complexité $C(N)$ d'un algorithme, on peut alors exécuter le code qui lui est associé et mesurer son temps d'exécution pour tracer la courbe de la complexité.

Complexité spatiale

Enfin, L'autre paramètre utile que l'on mesure est le nombre de cases mémoires utilisées par l'algorithme, c'est à dire la taille des variables dont il a eu besoin pour fonctionner.

Par exemple notre fonction fibonacci(n) nécessite $n+2$ cases mémoires, en plus de ses paramètres, pour fonctionner :

• 1 case mémoire pour le stockage du paramètre $n$
• $n$ cases pour le tableau
• 1 case pour le stockage de l'entier $i$

Comparez avec l'algorithme suivant qui calcule aussi le $n$ème élément de la suite de Fibonacci :

algorithme fibonacci_sobre(n):
  F ← un tableau de n entiers
  a ← 1
  b ← 1

  i ← 2
  tant que i < n :
    c ← a + b
    a ← b
    b ← c
    
    i ← i + 1

  rendre b

Il demande beaucoup moins de mémoire, 5 cases mémoires seulement (pour stocker le paramètre $n$ et les 4 variables $a$, $b$, $c$ et $i$), ce qui lui permet de calculer de grandes valeurs de la suite de Fibonacci, plus grande que la taille mémoire de l'ordinateur qui exécutera le code associé.

Complexité et complexité spatiale sont liées puisque chaque affectation d'une variable prend une instruction :