Next: La transformée de Fourier
Up: No Title
Previous: Diviser pour régner
Soit
la complexité dans le pire des cas de l'algorithme appliqué
à un problème de taille
. 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
. Enfin, on se donne la
complexité
sur un problème de taille 1. La complexité de
l'algorithme est donc déterminée par l'équation de récurrence suivante :
![\begin{displaymath}
T(n) = aT(n/b) + d(n)\end{displaymath}](img352.gif)
Résolvons ces équations quand
est une puissance de
; dans ce cas
l'équation s'écrit :
![\begin{displaymath}
T(b^p) = a T(b^{p-1}) + d(b^p)\end{displaymath}](img353.gif)
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}](img354.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}](img357.gif)
Discutons selon les valeurs relatives de
et
.
- Si
, cette somme vaut
;
donc
. Ainsi, si
et
(cas très usuel, en particulier de la FFT, du tri par fusion
et du tri rapide), on a
. Si
et
(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}](img368.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
(cas de la multiplication matricielle de Strassen, où
et
), 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
.
Next: La transformée de Fourier
Up: No Title
Previous: Diviser pour régner
R.Lalement (Cermics)