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'instruction 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
if ((x > 12) AND (x < 36)):
    z = "entre 13 et 35"

1. Création de l'entier valant 30 : 1 instruction
2. on affecte l'entier à x : 1 instruction
3. Pour faire cette instruction il faut :
   • 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
   • 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
   • faire l'instruction AND : 1 instruction
   • faire le if : 1 instruction
4. on commence par récupérer la valeur de x (1 instruction), on crée la chaîne (1 instruction) puis affecte le résultat d'une opération élémentaire (2 instructions) : donc un total de 4 instructions

Un nombre total d'instructions de 14.

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 :

def recherche(t, x):
    for e in t:
        if e == x:
            return True
    return False

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

1. exécution de la ligne 7 : création d'un tableau et affectation à une variable : 2 instructions
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 e : 1 instruction
      2. exécution de la ligne 2 (3 fois): affecter e : 1 instruction
      3. exécution de la ligne 3 : un test
         • on trouve les objets associées à t et e : 2 instructions
         • on teste l'égalité : 1 instruction
         • on fait le if : 1 instruction
      4. exécution de la ligne 4 : on arrive à cette ligne à la troisième itération : 1 instruction
   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 $2+2+1+\underbracket{(1+1+1+1+3 \cdot (2+1+1) + 1)}_{\mbox{recherche(t, 6)}} + 1 + 1$ instructions c'est à dire $24$ instructions.

Complexité des structures

TBD re-écrire sous la forme de structures avec l'exemple de la pile et de son implémentation sous la forme d'un tableau de taille fixe donné a la création et d'une méthode copie dans pile qui copie toute la structure dans une autre.

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.

Par exemple pour les listes, qui sont des tableaux redimensionnables :

• complexité d'ajout d'un élément à la fin de la liste : coût de 1 instruction
• complexité de l'ajout d'un élément pas à la fin de la liste : coût de la taille de la liste instructions
• complexité de la suppression d'un élément à la fin de la liste : coût de 1 instruction
• complexité de la suppression d'un élément pas à la fin de la liste : coût de la taille de la liste instructions
• usage comme un tableau : 1 instruction

Si vous utilisez des méthodes d'objets comme vous avez l'habitude de le faire en python (comme une ma_liste.index("?"), x in ma_chaîne_de_caractères) ou des structures compliquées (télécharger un fichier d'internet) vous avez le droit mais vous devez en connaître le coût : la complexité, les cas d'usage (comme être connecté à internet), etc.

Complexité d'un algorithme

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

F = un tableau vide de 10 cases
F[0] = 1
F[1] = 2

pour i allant de 2 à 9:
  F[i] = F[i-1] + F[i-2]

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 :

fonction fibonacci(n):
  F = un tableau vide de n cases
  F[0] = 1
  F[1] = 2

  pour i allant de 2 à n-1:
    F[i] = F[i-1] + F[i-2]

  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) = 5\cdot n+2$ 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éral. Par exemple l'algorithme suivant, écrit en python, qui cherche si une valeur est dans un tableau :

fonction est_dans_tableau(valeur, tableau):
    pour chaque élément x du tableau:
        si x == valeur:
            rend OUI
    rend NON

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 9 lorsque la valeur est le premier élément du tableau (les deux affectations des paramètres ; une affectation de $x$ ; deux lectures, une opération booléenne et un test ; une création d'objet puis un retour) à $5n + 4$ si la valeur n'est pas dans le tableau (les deux affectations des paramètres ; $n$ affectations de $x$ ; deux $n$ 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) = 5i + 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 la fonction est_dans_tableau 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 est_dans_tableau vaut $5N+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 est_dans_tableau par exemple), la complexité prend le maximum ($5N+4$ où $N$ est la la taille du tableau en entrée pour l'algorithme est_dans_tableau) mais il peut être utile de connaître le minimum ($9$ pour l'algorithme est_dans_tableau, 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 :

fonction fibonacci_sobre(n):
  a = 1
  b = 1

  pour i allant de 2 à n-1:
    c = a + b
    a = b
    b = c

  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é.

Sa complexité un peu plus élevée :

1. 1 instruction : affectation du paramètre
2. 2 instructions : création d'un objet et affectation
3. 2 instructions : création d'un objet et affectation
5. $n+2$ instructions : $n-2$ affectations de i et 4 instruction pour la création des bornes (2 créations (entiers 2 et 1) ; une lecture et une opération de soustraction)
6. $4(n-2)$ instructions : $n-2$ itérations de 2 lectures, une somme et une affectation
7. $2(n-2)$ instructions : $n-2$ itérations de 1 lecture et une affectation
8. $2(n-2)$ instructions : $n-2$ itérations de 1 lecture et une affectation
10. 2 instructions : 1 lecture, un retour

Pour un total de $9\cdot n-15$, mais reste comparable au premier.

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