on choisit un élément du tableau au hasard qui sera 'pivot' et on permute tous les éléments de manière à placer à gauche du pivot les éléments qui lui sont inférieurs, et à droite ceux qui lui sont supérieurs
on trie les deux moitiés de part et d'autre du pivot.
-
On peut utiliser un algorithme diviser pour régner pour effectuer la rotation d'une image d'un quart de tour.
Il s'agit d'un exemple pédagogique, enseigné par exemple en France en cours d'informatique au lycée[1]. Il est cependant, dans ce cas, inefficace en pratique. En effet, chaque pixel de l'image est déplacé autant de fois qu'il y a d'étapes Diviser alors qu'il serait possible avec d'autres algorithmes de placer directement chaque pixel à sa destination.
L'image à faire pivoter est partagée en quatre carreaux (diviser) et on déplace chaque carreau d'un quart de tour sans le faire tourner sur lui-même (régner) avant de réassembler les carreaux entre eux (combiner).
On s'arrête lorsque les carreaux ont une taille de un pixel.
Exécution d'un algorithme de rotation d'image d'un quart de tour avec Diviser pour régner.
La recherche dichotomique est formalisée dans un article de John Mauchly en 1946.
Cependant, l'idée d'utiliser une liste triée pour faciliter la recherche remonte à Babylone en -220[2].
L'algorithme d'Euclide pour calculer le plus grand commun diviseur de deux nombres peut être vu comme un algorithme diviser pour régner (les deux nombres diminuent et on se ramène à un problème plus petit).
Gauss décrit la transformée de Fourier rapide en 1805 [3] sans en faire l'analyse de complexité. La transformée de Fourier rapide est redécouverte un siècle plus tard.
La faible complexité des algorithmes diviser pour régner est l'un de leurs principaux intérêts[N 1].
Il existe plusieurs théorèmes facilitant le calcul des complexités des algorithmes de type diviser pour régner. Le principal théorème est le Master theorem. Pour des cas plus complexes on peut citer le théorème d'Akra-Bazzi.
La table suivante compare la complexité d'un algorithme naïf et de l'algorithme diviser pour régner pour quelques problèmes (voir Notations de Landau) :
Les algorithmes diviser pour régner se prêtent naturellement à une écriture récursive. Mais parfois, l'exécution d'algorithmes récursifs peut conduire à un dépassement de pile. On préfère donc parfois un algorithme itératif.
Sous-problèmes redondants
Lorsque l'on applique « diviser pour régner », il n'y a pas de redondance : chaque sous-problème n’est résolu qu'une seule fois lors des appels récursifs. Par contre, lorsque les sous-problèmes sont redondants, l'algorithme récursif obtenu à partir de « diviser pour régner » peut avoir une mauvaise complexité. Prenons l'exemple du calcul du nème terme de la suite de Fibonacci. L'algorithme suivant est en temps exponentiel en n :
fonction fibonacci(n)
si(n = 0 ou n = 1)
renvoyer 1
sinonrenvoyer fibonacci(n-1) + fibonacci(n-2)
Pour pallier cette limite, on peut mémoriser les valeurs déjà calculées afin d'éviter de résoudre les sous-problèmes déjà rencontrés. Il s'agit de la mémoïsation (aussi utilisée en programmation dynamique).
Notes et références
Notes
↑L'utilisation du paradigme diviser pour régner n'est pas une garantie absolue d'optimalité : des algorithmes comme le tri faire-valoir sont plus mauvais que des algorithmes naïfs bien qu'ils utilisent ce paradigme.
↑(en) M. T. Heideman, D. H. Johnson et C. S. Burrus, « Gauss and the history of the fast Fourier transform », IEEE ASSP Magazine, vol. 1, no 4, , p. 14-21.
↑(ru) Anatolii A. Karatsuba et Yuri P. Ofman, « Умножение многозначных чисел на автоматах », Doklady Akademii Nauk SSSR, vol. 146, , p. 293–294 (lire en ligne) traduit en anglais dans (en) « Multiplication of Multidigit Numbers on Automata », Physics-Doklady, vol. 7, , p. 595–596 (présentation en ligne).
