É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>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^2$.