next up previous contents index
suivant: La transformée de Fourier monter: main précédent: Diviser pour régner   Table des matières   Index


Équations de complexité

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 :

\begin{displaymath}
T(n) = aT(n/b) + d(n)
\end{displaymath}

Résolvons ces équations quand $n$ est une puissance de $b$ ; dans ce cas l'équation s'écrit :

\begin{displaymath}
T(b^p) = a T(b^{p-1}) + d(b^p)
\end{displaymath}

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}

Le premier terme, $a^p = a^{\log_b n} = n^{\log_b a}$ 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 $d(n) = n^\delta$. 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}

Discutons selon les valeurs relatives de $a$ et $b^\delta$.


next up previous contents index
suivant: La transformée de Fourier monter: main précédent: Diviser pour régner   Table des matières   Index
R Lalement