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 à ces 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²⁸, mais elle permet souvent une réduction importante de la complexité $T(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)$