Définitions

On appelle complexité le nombre d'instructions basiques utilisé pour exécuter un pseudo-code. La complexité est proportionnelle au temps mis pour l'exécuter en supposant que que toutes les instructions basiques prennent le même temps (au pire on prend le temps max).

Considérons par exemple le pseudo-code suivant :

ref age int
age ← 16
si ((age ≥ 12) ET (age < 18)):
    affiche "Tu es un adolescent."

Si on compte le nombre d'instructions utilisées pour son exécution :

• première ligne : 1 instruction, création de la variable age,
• deuxième ligne : 2 instructions
  1. Création de l'entier valant 16 : 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 affiche le résultat : 1 instruction

Sa complexité vaut le nombre total d'instructions, c'est à dire 13.

Complexité d'un pseudo-code

La notion d'instruction à effectuer dépend du pseudo-code utilisé. On verra plus tard un moyen radical de simplifier la définition (temps constant vs temps dépendant de paramètres) mais pour l'instant on va supposer qu'un instruction élémentaire correspond à celles que l'on a donné lorsque l'on a défini le pseudo-code :

• création d'une variable ou d'un objet
• affectation d'une variable
• trouver l'objet associé à une variable
• un test ou une opération arithmétique entre 2 objets
• l'affichage d'un objet à l'écran

Boucles

On compte bien toutes les instructions et pas seulement ceux qui le constitue, donc pour le pseudo-code suivant :

ref message ← "j'aime me répéter"
ref i ← 1
tant que i ≤ 10000:
    affiche message
    i ← i + 1

Chaque ligne va prendre :

• 3 instructions pour la première ligne : création de variable, de la chaîne et son affectation
• 3 instructions pour la deuxième ligne : création de variable, de la chaîne et son affectation
• 4 instructions pour la troisième ligne : recherche de la variable, création de l'entier, test et saut si nécessaire
• 2 instructions pour la quatrième ligne : recherche de la variable et affichage
• 4 instructions pour la quatrième ligne : recherche de la variable, création de l'entier, addition et affectation

Mais comme les lignes 4, et 5 sont exécutées 10000 fois et la ligne 3 10001 fois (ne pas oublier le test final lorsque $i > 10000$), la complexité du pseudo-code vaut :

Utilisation de tableaux

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

La création d'un objet de type tableau revient à créer autant de variables qu'il a d'indices puisqu'il faut mettre toutes ses valeurs à ∅ (aucun objet n'est encore associé aux valeurs du tableau). Ainsi, dans notre modèle de pseudo-code, la création d'un tableau prend autant d'instructions que sa longueur.

L'accès à un indice particulier du tableau est rapide et ne nécessite qu'une seule instruction. Ainsi :

• 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 une variable de type tableau nécessite 1 instruction
• créer un tableau de taille 42 nécessite 42 instructions
• afficher F[3] nécessite 2 instructions : une pour retrouver l'objet associé à F[3] et l'autre pour l'afficher (on accède au quatrième élément du tableau, d'indice valant 3, on n'a pas besoin de créer un entier valant 3)
• F[3] ← 42 nécessite aussi 2 instructions : une pour créer l'entier 42 l'autre pour l'affecter au quatrième élément du tableau
• F[i] ← 42 nécessite en revanche 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 127 instructions :
  • 42 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)

Appels de fonctions

La plupart du temps on utilise plus que les instructions basiques comme des fonctions que l'on suppose accessible (comme le min ou le max) ou des algorithmes que l'on a défini nous même. Il ne faut pas oublier d'ajouter leurs complexités au calcul.

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

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

ref T []int
T ← [1, 2, 6]
ref trouve int
trouve ← recherche(T, 6)
affiche trouve

1. exécution de la ligne 7 : 1 instructions ; création d'une variable tableau
2. exécution de la ligne 8 : 10 instructions
   • création et initialisation à ∅ d'un tableau à 3 indices
   • 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+10+1+\underbracket{(4 + 1 + 3 \cdot (4+4) + 2)}_{\mbox{recherche(t, 6)}} + 1 + 2$ instructions c'est à dire $46$ instructions.

Complexité d'un algorithme

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

ref F []int
F ← [10]int
F[0] ← 1
F[1] ← 1

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

rendre F[9]

Mais souvent on ne va pas utiliser juste un pseudo-code, on crée des algorithmes pour être utilisé avec différents objets, ou dans d'autres algorithmes. On ne cherche alors plus à calculer la complexité de l'exécution effective d'un pseudo-code mais de l'exécution potentielle d'un code selon ses paramètres.

Transformons le pseudo-code précédent en algorithme pour qu'il puisse calculer tous les fermes de la suite de Fibonacci et pas uniquement le 10ème :

algorithme fibonacci(n: int) → int:
    ref F []int
    F ← [n]int
    F[0] ← 1
    F[1] ← 1

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

    rendre F[-1]

Le nombre de fois où l'on rentre dans la boucle va dépendre de l'entrée $n$ et on a maintenant une complexité de :

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

algorithme recherche(T: []int, x: int) → bool:
    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 longueur $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 T et x ; 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) à $6\cdot n + 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 tableau et un entier en paramètres mais pas la nature des entiers contenus dans le tableau. Avoir une complexité qui dépend des valeurs contenues dans le tableau est donc inutile en pratique. Il est plus intéressant de connaître la complexité de l'algorithme pour un tableau d'une longueur donnée.

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, les booléens, les approximation de réels et les caractères qui sont stockable sur 1 unité de mémoire,
• les tableaux et les chaînes de caractères dont la taille est leur longueur multiplié par la taille de leurs 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 longueur 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 prise 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 $18n - 21$.

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):
  ref a ← 1
  ref b ← 1
  ref c int

  ref 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, 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 :

La proposition précédente est très générale puisqu'on a vu que tout algorithme peut être écrit comme n'utilisant que des []bit.