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 :

age := entier
age ← 16
si ((age ≥ 12) et (age < 18)):
    personne ← "adolescent"

• première ligne : 1 instruction, création de la variable age,
• deuxième ligne : 2 instructions
  1. Création de l'entier valant 42 : 1 instruction
  2. on affecte l'entier à la variable age : 1 instruction
• troisième ligne : 8 instructions
  1. faire age ≥ 12. Pour cela :
     • on crée l'entier valant 12 : 1 instruction
     • on récupère la valeur de age : 1 instruction
     • on effectue la comparaison : 1 instruction
  2. faire age < 18. Pour cela :
     • on crée l'entier valant 18 : 1 instruction
     • on récupère la valeur de age : 1 instruction
     • on effectue la comparaison : 1 instruction
  3. faire l'instruction et : 1 instruction
  4. faire l'instruction 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 13 pour ces quatre 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.

Reprenons par exemple le code de l'algorithme recherche et comptons les instructions utilisées au cours de son exécution :

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

T := [entier] 
T ← [1, 2, 6]
trouve := entier
trouve ← recherche(T, 6)
affiche à l'écran trouve

1. exécution de la ligne 7 : 1 instructions ; création d'une variable tableau
2. exécution de la ligne 8 : 7 instructions
   • création de 3 entiers : 3 instructions
   • affectation des 3 entiers aux indices du tableau : 3 instructions
   • affectation du tableau à une variable : 1 instruction
3. exécution de la ligne 9 : 1 instructions ; création d'une variable
4. exécution de la ligne 10 :
   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)
         1. uniquement la première fois : on crée la variable e ; 1 instruction
         2. les 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 : 1 instruction
5. afficher quelque chose à l'écran :
   • 1 instruction pour trouver l'objet à afficher
   • 1 instruction pour trouver l'afficher

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

Complexité des accès à un tableau ?

Combien d'instructions nécessitent 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
• 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.
• F ← [1 .. 42] nécessite 86 instructions :
  • 1 pour la création de l'objet tableau de longueur 42
  • 42 pour la création des entiers allant de 1 à 42
  • 42 pour l'affectation des entiers aux éléments du tableau
  • 1 pour l'affectation du tableau à la variable F (que l'on suppose déjà créée)

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 := [entier]
F ← [entier]{longueur: 10}
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 := [entier]
  F ← [entier]{longueur: n}
  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-19$ 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 := entier) 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 11 lorsque la valeur est le premier élément du tableau (les deux affectations des paramètres ; la création de e ; 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 + 5$ si la valeur n'est pas dans le tableau (les deux affectations des paramètres ; la création de e ; $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 + 5$ 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 leur longueur multiplié par la taille d'une de ses données.

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+5$, en utilisant la taille du tableau passé en entrée comme paramètre : pour tout tableau de longueur $N$ passé en paramètre, la complexité maximale est de $6N+5$ instructions.

Lorsque les données sont de taille fixe, on ne peut pas utiliser la taille prises par les données comme paramètre. C'est le cas de la fonction fibonacci(n), puisque pour nous la taille de stockage d'un entier sera toujours de 1. On peut alors souvent utiliser la valeur elle même des données comme paramètre, ce qui donne : pour des données de valeur $n$ la complexité de l'algorithme est de de $17n -19$.

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+5$ 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):
  (a := entier) ← 1
  (b := entier) ← 1
  c := entier

  (i := entier) ← 2
  tant que i < n :
    c ← a + b
    a ← b
    b ← c
    
    i ← i + 1

  rendre b

Il demande beaucoup moins de mémoire, 4 cases mémoires seulement pour stocker les 4 variables ($a$, $b$, $c$ et $i$), sans compter le paramètre $n$, 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 :

On peut même avoir un encadrement plus précis :