Next: La transformée de Fourier
Up: No Title
Previous: Diviser pour régner
Soit T(n) la complexité dans le pire des cas de l'algorithme appliqué
à un problème de taille n. On suppose que la complexité des opérations
de décomposition du problème et de recomposition des solutions des
sous-problèmes a une complexité en d(n). Enfin, on se donne la
complexité T(1) sur un problème de taille 1. La complexité de
l'algorithme est donc déterminée par l'équation de récurrence suivante :
T(n) = aT(n/b) + d(n)
Résolvons ces équations quand n est une puissance de b ; dans ce cas
l'équation s'écrit :
T(bp) = a T(bp-1) + d(bp)
Sa solution est
![\begin{displaymath}
T(b^p) = a^p T(1) + \sum_{j=0}^{p-1} a^j d(b^{p-j})\end{displaymath}](img229.gif)
Le premier terme,
correspond à la
complexité due à la résolution de tous les sous-problèmes ; le second
terme est la complexité due à toutes les opérations de
décomposition/recomposition.
Examinons ce deuxième terme quand
. On a
![\begin{displaymath}
\sum_{j=0}^{p-1} a^j d(b^{p-j}) =
b^{p\delta} \sum_{j=0}^{p-1}(\frac{a}{b^\delta})^j\end{displaymath}](img232.gif)
Discutons selon les valeurs relatives de a et
.
- Si
, cette somme vaut
;
donc
. Ainsi, si
et a=b (cas très usuel, en particulier de la FFT, du tri par fusion
et du tri rapide), on a
. Si
et a=1 (cas de la recherche dichotomique), on
obtient
. -
Si
,
![\begin{displaymath}
b^{p\delta} \sum_{j=0}^{p-1}(\frac{a}{b^\delta})^j =
b^{p\de...
... -1}{a/b^\delta -1} =
\frac{a^p - b^{p\delta}}{a/b^\delta -1}.\end{displaymath}](img242.gif)
- Si
, le terme dominant est
, qui
est indépendant de
et qui est du même ordre que le premier
terme, donc
. Ainsi, si
et
a>b (cas de la multiplication matricielle de Strassen, où
a=7 et b=2), on a
. -
Si
, le terme dominant est
, donc
. La décomposition du problème ne conduit
dans ce dernier cas à aucune accélération, les opérations de
décomposition et recomposition étant dominantes. C'est le cas de
l'équation T(n) = 2T(n/2) + n2.
Next: La transformée de Fourier
Up: No Title
Previous: Diviser pour régner
Jean-Philippe Chancelier
9/29/1998