1. Problèmes numériques
23
c’est-à-dire s’il existe deux constantes f et q 0 telles que
W (q) fi (q)
;q q 0
Dans une méthode à accès direct, une donnée est localisée en R(1) opérations. L’accès dans un arbre de recherche est en R(orjq). Une addition
polynomiale est en R(q). Un tri récursif ou une transformée de Fourier rapide sont en R(qorjq). Une multiplication matricielle en R(q
2 ).D o n n o n s
un exemple simple de calcul de complexité.
Exemple. Considérons l’algorithme récursif du calcul de q !
FAIRE
(1)
SI (q 1) ALORS
(2)
idfw =1
(3)
SINON idfw(q)=q idfw(q 1)
FIN FAIRE
L e sl i g n e s( 1 )e t( 2 )o n tu n ec o m p l e x i t ée nR(1), la ligne (3) est en R(1)
+W (q 1).P a rc o n s é q u e n t ,s il en o m b r ef désigne le nombre d’opérations en R(1) et si qA1> alors W (q)=f + W (q 1)= En définitive, W (q)
= f(q 1) + W (1),d ’ o ùW (q)=R(q). L’algorithme récursif du calcul de
factoriel q est donc en R(q).
1.5 Optimisation
En pratique, le choix d’un algorithme n’est pas toujours un problème
simple. On cherchera l’algorithme qui donne la meilleure précision sur les
résultats obtenus et qui minimise l’encombrement mémoire et le temps
de calcul. L’optimisation cherche à réduire le nombre d’opérations et en
premier lieu le nombre de multiplications. Donnons deux exemples dans
lesquels on cherche à diminuer le nombre de multiplications, quitte à les
remplacer par des additions, moins coûteuses en temps de calcul.
Exemple 1.Leproduitdedeuxnombrescomplexes} 1 = d+le et } 2 = f+lg
nécessite l’évaluation de quatre quantités df, eg, dg et ef. En écrivant :
df eg =(d + e)f e(f + g)
dg + ef =(d e)g e(f + g)
on diminue le calcul à l’évaluation de trois quantités : (d + e)f, (d e)g
et e(f + g). Le gain vient du fait qu’une multiplication est beaucoup plus
lente qu’une addition.
23
c’est-à-dire s’il existe deux constantes f et q 0 telles que
W (q) fi (q)
;q q 0
Dans une méthode à accès direct, une donnée est localisée en R(1) opérations. L’accès dans un arbre de recherche est en R(orjq). Une addition
polynomiale est en R(q). Un tri récursif ou une transformée de Fourier rapide sont en R(qorjq). Une multiplication matricielle en R(q
2 ).D o n n o n s
un exemple simple de calcul de complexité.
Exemple. Considérons l’algorithme récursif du calcul de q !
FAIRE
(1)
SI (q 1) ALORS
(2)
idfw =1
(3)
SINON idfw(q)=q idfw(q 1)
FIN FAIRE
L e sl i g n e s( 1 )e t( 2 )o n tu n ec o m p l e x i t ée nR(1), la ligne (3) est en R(1)
+W (q 1).P a rc o n s é q u e n t ,s il en o m b r ef désigne le nombre d’opérations en R(1) et si qA1> alors W (q)=f + W (q 1)= En définitive, W (q)
= f(q 1) + W (1),d ’ o ùW (q)=R(q). L’algorithme récursif du calcul de
factoriel q est donc en R(q).
1.5 Optimisation
En pratique, le choix d’un algorithme n’est pas toujours un problème
simple. On cherchera l’algorithme qui donne la meilleure précision sur les
résultats obtenus et qui minimise l’encombrement mémoire et le temps
de calcul. L’optimisation cherche à réduire le nombre d’opérations et en
premier lieu le nombre de multiplications. Donnons deux exemples dans
lesquels on cherche à diminuer le nombre de multiplications, quitte à les
remplacer par des additions, moins coûteuses en temps de calcul.
Exemple 1.Leproduitdedeuxnombrescomplexes} 1 = d+le et } 2 = f+lg
nécessite l’évaluation de quatre quantités df, eg, dg et ef. En écrivant :
df eg =(d + e)f e(f + g)
dg + ef =(d e)g e(f + g)
on diminue le calcul à l’évaluation de trois quantités : (d + e)f, (d e)g
et e(f + g). Le gain vient du fait qu’une multiplication est beaucoup plus
lente qu’une addition.