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)$