30
1 Ce qu’on ne peut ignorer
plus généralement, une complexité polynomiale s’il requiert O(d
m ) opérations, où m est un entier positif. Des algorithmes peuvent aussi avoir
une complexité exponentielle (O(c
d ) opérations) ou même factorielle
(O(d!) opérations). Rappelons que l’écriture O(d
m ) signifie “se comporte,
pour de grandes valeurs de d, comme une constante fois d
m ”.
Exemple 1.2 (Produit matrice-vecteur) Soit A une matrice carrée d’ordre
n et soit v ∈ R
n : la j−ème composante du produit Av est donnée par
aj1v1 + aj2v2 + . . . + ajnvn,
ce qui nécessite n produits et n − 1 additions. On effectue donc n(2n − 1)
opérations pour calculer toutes les composantes. Cet algorithme requiert O(n
2 )
opérations, il a donc une complexité quadratique par rapport au paramètre n.
Le même algorithme nécessiterait O(n
3 ) opérations pour calculer le produit de
deux matrices d’ordre n. Il y a un algorithme, dû à Strassen, qui ne requiert
“que” O(n
log 2 7 ) opérations, et un autre, dû à Winograd et Coppersmith, en
O(n
2.376 ) opérations.
Exemple 1.3 (Calcul du déterminant d’une matrice) On a vu plus haut
que le déterminant d’une matrice carrée d’ordre n peut être calculé en utilisant
la formule de récurrence (1.8). L’algorithme correspondant a une complexité
factorielle en n et ne serait utilisable que pour des matrices de très petite
dimension. Par exemple, si n = 24, il faudrait 59 ans à un ordinateur capable d’atteindre 1 Peta-flops (i.e. 10
15 opérations par seconde). Il est donc
nécessaire de recourir à des algorithmes plus efficaces. Il existe des méthodes
permettant le calcul de déterminants à l’aide de produits matrice-matrice, avec
une complexité de O(n
log 2 7 ) opérations en utilisant l’algorithme de Strassen
déjà mentionné (voir [BB96]).
Le nombre d’opérations n’est pas le seul paramètre à prendre en
compte dans l’analyse d’un algorithme. Un autre facteur important est
le temps d’accès à la mémoire de l’ordinateur (qui dépend de la manière
dont l’algorithme a été programmé). Un indicateur de la performance
d’un algorithme est donc le temps CPU (CPU vient de l’anglais central
processing unit ), c’est-à-dire le temps de calcul. En MATLAB, il peut
être obtenu avec la commande cputime. Le temps total écoulé entre les
cputime
phases d’entrée et de sortie peut être obtenu avec la commande etime.
etime
Exemple 1.4 Pour calculer le temps nécessaire à un produit matrice-vecteur,
on considère le programme suivant :
>> n=10000; step=100;
>> A=rand(n,n);
>> v=rand(n,1);
>> T=[ ];
>> sizeA=[ ];
>> for k = 500:step:n
AA = A(1:k,1:k);
1 Ce qu’on ne peut ignorer
plus généralement, une complexité polynomiale s’il requiert O(d
m ) opérations, où m est un entier positif. Des algorithmes peuvent aussi avoir
une complexité exponentielle (O(c
d ) opérations) ou même factorielle
(O(d!) opérations). Rappelons que l’écriture O(d
m ) signifie “se comporte,
pour de grandes valeurs de d, comme une constante fois d
m ”.
Exemple 1.2 (Produit matrice-vecteur) Soit A une matrice carrée d’ordre
n et soit v ∈ R
n : la j−ème composante du produit Av est donnée par
aj1v1 + aj2v2 + . . . + ajnvn,
ce qui nécessite n produits et n − 1 additions. On effectue donc n(2n − 1)
opérations pour calculer toutes les composantes. Cet algorithme requiert O(n
2 )
opérations, il a donc une complexité quadratique par rapport au paramètre n.
Le même algorithme nécessiterait O(n
3 ) opérations pour calculer le produit de
deux matrices d’ordre n. Il y a un algorithme, dû à Strassen, qui ne requiert
“que” O(n
log 2 7 ) opérations, et un autre, dû à Winograd et Coppersmith, en
O(n
2.376 ) opérations.
Exemple 1.3 (Calcul du déterminant d’une matrice) On a vu plus haut
que le déterminant d’une matrice carrée d’ordre n peut être calculé en utilisant
la formule de récurrence (1.8). L’algorithme correspondant a une complexité
factorielle en n et ne serait utilisable que pour des matrices de très petite
dimension. Par exemple, si n = 24, il faudrait 59 ans à un ordinateur capable d’atteindre 1 Peta-flops (i.e. 10
15 opérations par seconde). Il est donc
nécessaire de recourir à des algorithmes plus efficaces. Il existe des méthodes
permettant le calcul de déterminants à l’aide de produits matrice-matrice, avec
une complexité de O(n
log 2 7 ) opérations en utilisant l’algorithme de Strassen
déjà mentionné (voir [BB96]).
Le nombre d’opérations n’est pas le seul paramètre à prendre en
compte dans l’analyse d’un algorithme. Un autre facteur important est
le temps d’accès à la mémoire de l’ordinateur (qui dépend de la manière
dont l’algorithme a été programmé). Un indicateur de la performance
d’un algorithme est donc le temps CPU (CPU vient de l’anglais central
processing unit ), c’est-à-dire le temps de calcul. En MATLAB, il peut
être obtenu avec la commande cputime. Le temps total écoulé entre les
cputime
phases d’entrée et de sortie peut être obtenu avec la commande etime.
etime
Exemple 1.4 Pour calculer le temps nécessaire à un produit matrice-vecteur,
on considère le programme suivant :
>> n=10000; step=100;
>> A=rand(n,n);
>> v=rand(n,1);
>> T=[ ];
>> sizeA=[ ];
>> for k = 500:step:n
AA = A(1:k,1:k);