Diviser pour régner

Un algorithme diviser pour régner a la structure suivante : pour résoudre un problème de taille n, l'algorithme consiste à décomposer le problème en a sous-problèmes ayant tous la taille n/b (peut-être approximativement), à appliquer l'algorithme à tous les sous-problèmes, puis à construire une solution du problème en composant les solutions des sous-problèmes. Non seulement cette méthode est naturelle (et voisine du second précepte de la méthode de Descartes), mais elle permet souvent une réduction importante de 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)

Voici quelques exemples :

•     recherche dichotomique dans une table ordonnée (a=1, b=2) : $T(n) = T(n/2) + \Theta(1)$, d'où $T(n) = \Theta(\log n)$, alors qu'une recherche séquentielle dans une table ordonnée est en $\Theta(n)$ ;
•   tri d'une table par fusion (a=2, b=2) : $T(n) = 2T(n/2) + \Theta(n)$, d'où $T(n) = \Theta(n\log n)$, alors qu'un tri ordinaire est typiquement en $\Theta(n^2)$ ;
•   transformée de Fourier rapide (a=2, b=2) : $T(n) = 2T(n/2) + \Theta(n)$, d'où $T(n) = \Theta(n\log n)$, alors qu'une évaluation directe des formules est en $\Theta(n^2)$ ;
• multiplication de deux matrices par l'algorithme de Strassen (a=7, b=2) : $T(n) = 7T(n/2) + \Theta(n^2)$, d'où $T(n) = \Theta(n^{\log 7}) \approx \Theta(n^{2,81})$ alors que la multiplication ordinaire est en $\Theta(n^3)$.

   

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\del... ...-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².