É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 :

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(b^p) = a T(b^p-1) + d(b^p)

Sa solution est

$$T(b^p) = a^p T(1) + \sum_{j=0}^{p-1} a^j d(b^{p-j})$$

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

$$\sum_{j=0}^{p-1} a^j d(b^{p-j}) = b^{p\delta} \sum_{j=0}^{p-1}(\frac{a}{b^\delta})^j$$

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

• Si $a=b^\delta$, cette somme vaut $b^{p\delta}p = n^\delta \log_b n$ ; donc $T(n) = n^{\log_b a} T(1) + n^\delta \log_b n$. Ainsi, si $\delta = 1$ et a=b (cas très usuel, en particulier de la FFT, du tri par fusion et du tri rapide), on a $T(n) = n T(1) + n \log_b n = \Theta(n \log_b n)$. Si $\delta = 0$ et a=1 (cas de la recherche dichotomique), on obtient $T(n) = \log_b n$.
• Si $a\not=b^\delta$,

  $$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}.$$

• Si $a\gt b^\delta$, le terme dominant est $a^p = n^{\log_b a}$, qui est indépendant de $\delta$ et qui est du même ordre que le premier terme, donc $T(n) = \Theta(n^{\log_b a})$. Ainsi, si $\delta = 1$ et a>b (cas de la multiplication matricielle de Strassen, où a=7 et b=2), on a $T(n) = \Theta(n^{\log_b a})$.
• Si $a<b^\delta$, le terme dominant est $b^{p\delta} = n^{\delta}$, donc $T(n) = \Theta(n^{\delta})$. 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) + n².