2.1 Complexité des Algorithmes
45
© Dunod – Toute reproduction non autorisée est un délit.
1. pour i d 1 à n
2. pour j d 1 à n
3.
C 1 i, j2 d 0
4.
pour k d 1 à n
5.
C 1 i, j2 d C 1 i, j2 1 A1 i, k2 3 B 1 k, j2 (où 3 a la priorité sur 1).
Considérons, pour débuter l’étude de complexité, la ligne 5 de l’algorithme. Lors
d’une exécution de cette instruction, il doit être effectué la lecture des trois valeurs
C(i, j), A(i, k), B(k, j), une multiplication et une addition, et l’écriture de la nouvelle
valeur de C(i, j). Ainsi, six opérations élémentaires sont nécessaires pour l’exécution de cette instruction. Notre objectif étant de déterminer le temps de calcul de
l’algorithme à une constante multiplicative près, nous estimerons à O(1) le nombre
constant d’opérations de l’instruction 5. Cette ligne 5 est exécutée n fois consécutivement au cours de l’exécution de la ligne 4, donc une exécution de la ligne 4 suivie
de la ligne 5 correspondra à O(n) opérations élémentaires. De façon analogue, la
ligne 2 sera exécutée n fois au cours de chaque exécution de la boucle de la ligne 1,
la ligne 3 exécutant O(1) opération, pour chacune des exécutions de la boucle 1, il y
a n 1 O1 12 1 O1 n2 2 5 O1 n
2
2 opérations effectuées. L’instruction 1 étant, elle-même,
exécutée n fois, la complexité de l’algorithme est O1 n
3
2 .
Remarque. Un autre algorithme, dû à Strassen, de complexité O1 n
2.81
2 a été
conçu pour effectuer la multiplication de matrices. Le lecteur intéressé par cet
algorithme plus sophistiqué et son calcul de complexité pourra consulter les
ouvrages d’algorithmique référencés en bibliographie ; 2,81 . log 2 7.
2.1.4 Les différentes mesures de complexité
Contrairement à l’exemple présenté plus haut qui, pour une valeur n donnée, exécute toujours le même nombre d’opérations élémentaires, un algorithme peut avoir des
comportements fort différents pour des données différentes de taille identique. Considérons comme exemple l’algorithme suivant qui détermine quelle est la position de la
valeur v dans un tableau T contenant n valeurs, sachant que v apparaît une et une seule
fois dans T.
1. i d 1
2. tant que T 1 i 2 2 v
3. i d i 1 1
4. sortir i
Le nombre d’opérations élémentaires exécutées dépend de la position de v dans
le tableau. En effet plus la position de v est éloignée du début de T, plus le nombre de
passages dans la boucle 2 sera important.
Nous allons alors définir trois notions différentes de complexité, la complexité dans
le pire des cas, la complexité dans le meilleur des cas et la complexité en moyenne.
Ces trois définitions complémentaires de complexité permettent au chercheur
45
© Dunod – Toute reproduction non autorisée est un délit.
1. pour i d 1 à n
2. pour j d 1 à n
3.
C 1 i, j2 d 0
4.
pour k d 1 à n
5.
C 1 i, j2 d C 1 i, j2 1 A1 i, k2 3 B 1 k, j2 (où 3 a la priorité sur 1).
Considérons, pour débuter l’étude de complexité, la ligne 5 de l’algorithme. Lors
d’une exécution de cette instruction, il doit être effectué la lecture des trois valeurs
C(i, j), A(i, k), B(k, j), une multiplication et une addition, et l’écriture de la nouvelle
valeur de C(i, j). Ainsi, six opérations élémentaires sont nécessaires pour l’exécution de cette instruction. Notre objectif étant de déterminer le temps de calcul de
l’algorithme à une constante multiplicative près, nous estimerons à O(1) le nombre
constant d’opérations de l’instruction 5. Cette ligne 5 est exécutée n fois consécutivement au cours de l’exécution de la ligne 4, donc une exécution de la ligne 4 suivie
de la ligne 5 correspondra à O(n) opérations élémentaires. De façon analogue, la
ligne 2 sera exécutée n fois au cours de chaque exécution de la boucle de la ligne 1,
la ligne 3 exécutant O(1) opération, pour chacune des exécutions de la boucle 1, il y
a n 1 O1 12 1 O1 n2 2 5 O1 n
2
2 opérations effectuées. L’instruction 1 étant, elle-même,
exécutée n fois, la complexité de l’algorithme est O1 n
3
2 .
Remarque. Un autre algorithme, dû à Strassen, de complexité O1 n
2.81
2 a été
conçu pour effectuer la multiplication de matrices. Le lecteur intéressé par cet
algorithme plus sophistiqué et son calcul de complexité pourra consulter les
ouvrages d’algorithmique référencés en bibliographie ; 2,81 . log 2 7.
2.1.4 Les différentes mesures de complexité
Contrairement à l’exemple présenté plus haut qui, pour une valeur n donnée, exécute toujours le même nombre d’opérations élémentaires, un algorithme peut avoir des
comportements fort différents pour des données différentes de taille identique. Considérons comme exemple l’algorithme suivant qui détermine quelle est la position de la
valeur v dans un tableau T contenant n valeurs, sachant que v apparaît une et une seule
fois dans T.
1. i d 1
2. tant que T 1 i 2 2 v
3. i d i 1 1
4. sortir i
Le nombre d’opérations élémentaires exécutées dépend de la position de v dans
le tableau. En effet plus la position de v est éloignée du début de T, plus le nombre de
passages dans la boucle 2 sera important.
Nous allons alors définir trois notions différentes de complexité, la complexité dans
le pire des cas, la complexité dans le meilleur des cas et la complexité en moyenne.
Ces trois définitions complémentaires de complexité permettent au chercheur