Next: Équations de complexité
Up: No Title
Previous: Opérations bit à bit
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 naturelle, 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
R.Lalement (Cermics)