Chapitre 2 • Notions de complexité
44
n 5 10
n 5 100
n 5 1 000
n 5 10
6
n 5 10
9
f 1 n2 5 log n
10
29
s
2 # 10
29
s
3 # 10
29
s
6 # 10
29
s
9 # 10
29
s
f 1 n2 5 n
10
28
s
10
27
s
10
26
s
10
23
s
1 s
f 1 n2 5 n log n
10
28
s
2 # 10
27
s
3 # 10
26
s
6 # 10
23
s
9 s
f 1 n2 5 n
2
10
27
s
10
25
s
10
23
s
1 000 s
32 ans
f 1 n2 5 n
3
10
26
s
10
23
s
1 s
32 ans 32 # 10
9
ans
f 1 n2 5 n
5
10
24
s
10 s
11 jours 3 # 10
13
ans
3 # 10
34
ans
f 1 n2 5 2
n
10
26
s 3 # 10
14
ans 10
281
siècles 10
3 # 10
5 siècles 10
3 # 10
8 siècles
Nous avons renoncé à ajouter une ligne f 1 n 2 5 n! à ce tableau, tant la croissance de
la factorielle est rapide.
2.1.2 Le codage des données
Avant la résolution proprement dite d’un problème, une première étape consiste à
stocker en mémoire les données du problème à traiter, afin de pouvoir les lire au
cours du traitement. La comparaison de deux algorithmes résolvant un même problème se fera par l’intermédiaire d’un même paramètre que nous appellerons “taille”
de la donnée d’entrée qui correspond, à une constante multiplicative près, aux nombres de bits nécessaires à l’écriture de cette donnée (en pratique, l’espace mémoire
pour stocker cette donnée). Un même objet mathématique pouvant être représenté
sous différentes formes (voir, par exemple, le chapitre consacré à la représentation
en machine d’un graphe), nous prendrons garde à ce que le codage de cette donnée
soit fait de manière raisonnable, ainsi un entier n pourra être représenté en binaire ou
en hexadécimal, mais en aucun cas en unaire (par n bâtons, comme le faisaient nos
lointains ancêtres).
Comme exemple considérons un algorithme effectuant la multiplication de deux
matrices de format carré n 3 n. Le nombre d’éléments de chaque matrice est donc
n
2
. En supposant que chaque élément de la matrice soit un entier de valeur bornée
par une constante K (ceci à fin d’éviter le cas de nombres très grands demandant
éventuellement quelques milliards de caractères pour être écrits), une matrice pourra
être codée en utilisant n
2
3log 2 K 4 caractères binaires ; donc la donnée d’entrée du
problème sera de taille 2n
2
3log 2 K 4 soit O1 n
2
2 .
([x] désigne la partie entière supérieure de x, par exemple : 37, 344 5 8).
2.1.3 Le temps de calcul
Nous allons, à travers un exemple simple, estimer le temps nécessaire à l’exécution
d’un algorithme. Dans ce but, nous compterons le nombre d’opérations élémentaires
effectuées à chaque étape de l’algorithme. Considérons l’algorithme suivant calculant C, la matrice résultat de la multiplication de deux matrices carrées A et B de
taille n si K 5 2
p
, 3log 2 k4 5 p, mais il faut p+1 bits pour le coder.
44
n 5 10
n 5 100
n 5 1 000
n 5 10
6
n 5 10
9
f 1 n2 5 log n
10
29
s
2 # 10
29
s
3 # 10
29
s
6 # 10
29
s
9 # 10
29
s
f 1 n2 5 n
10
28
s
10
27
s
10
26
s
10
23
s
1 s
f 1 n2 5 n log n
10
28
s
2 # 10
27
s
3 # 10
26
s
6 # 10
23
s
9 s
f 1 n2 5 n
2
10
27
s
10
25
s
10
23
s
1 000 s
32 ans
f 1 n2 5 n
3
10
26
s
10
23
s
1 s
32 ans 32 # 10
9
ans
f 1 n2 5 n
5
10
24
s
10 s
11 jours 3 # 10
13
ans
3 # 10
34
ans
f 1 n2 5 2
n
10
26
s 3 # 10
14
ans 10
281
siècles 10
3 # 10
5 siècles 10
3 # 10
8 siècles
Nous avons renoncé à ajouter une ligne f 1 n 2 5 n! à ce tableau, tant la croissance de
la factorielle est rapide.
2.1.2 Le codage des données
Avant la résolution proprement dite d’un problème, une première étape consiste à
stocker en mémoire les données du problème à traiter, afin de pouvoir les lire au
cours du traitement. La comparaison de deux algorithmes résolvant un même problème se fera par l’intermédiaire d’un même paramètre que nous appellerons “taille”
de la donnée d’entrée qui correspond, à une constante multiplicative près, aux nombres de bits nécessaires à l’écriture de cette donnée (en pratique, l’espace mémoire
pour stocker cette donnée). Un même objet mathématique pouvant être représenté
sous différentes formes (voir, par exemple, le chapitre consacré à la représentation
en machine d’un graphe), nous prendrons garde à ce que le codage de cette donnée
soit fait de manière raisonnable, ainsi un entier n pourra être représenté en binaire ou
en hexadécimal, mais en aucun cas en unaire (par n bâtons, comme le faisaient nos
lointains ancêtres).
Comme exemple considérons un algorithme effectuant la multiplication de deux
matrices de format carré n 3 n. Le nombre d’éléments de chaque matrice est donc
n
2
. En supposant que chaque élément de la matrice soit un entier de valeur bornée
par une constante K (ceci à fin d’éviter le cas de nombres très grands demandant
éventuellement quelques milliards de caractères pour être écrits), une matrice pourra
être codée en utilisant n
2
3log 2 K 4 caractères binaires ; donc la donnée d’entrée du
problème sera de taille 2n
2
3log 2 K 4 soit O1 n
2
2 .
([x] désigne la partie entière supérieure de x, par exemple : 37, 344 5 8).
2.1.3 Le temps de calcul
Nous allons, à travers un exemple simple, estimer le temps nécessaire à l’exécution
d’un algorithme. Dans ce but, nous compterons le nombre d’opérations élémentaires
effectuées à chaque étape de l’algorithme. Considérons l’algorithme suivant calculant C, la matrice résultat de la multiplication de deux matrices carrées A et B de
taille n si K 5 2
p
, 3log 2 k4 5 p, mais il faut p+1 bits pour le coder.