suivant: Équations de complexité
monter: main
précédent: Opérations bit à bit
  Table des matières
  Index
Diviser pour régner
Un algorithme diviser pour régner a la structure suivante : pour
résoudre un problème de taille
, l'algorithme consiste à décomposer
le problème en
sous-problèmes ayant tous la taille
(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 naturelle28, mais
elle permet souvent une réduction importante de la complexité
.
Voici quelques exemples :
-
recherche dichotomique dans une table ordonnée (
,
) :
, d'où
, alors qu'une
recherche séquentielle dans une table ordonnée est en 
-
tri d'une table par fusion (
,
) :
, d'où
, alors qu'un
tri ordinaire est typiquement en 
-
transformée de Fourier rapide (
,
) :
, d'où
, alors qu'une
évaluation directe des formules est en 
- multiplication de deux matrices par l'algorithme de Strassen
(
,
) :
, d'où
alors que la multiplication
ordinaire est en 
suivant: Équations de complexité
monter: main
précédent: Opérations bit à bit
  Table des matières
  Index
R Lalement