Diviser pour régner (informatique)
Un article de Wikipédia, l'encyclopédie libre.
Diviser pour régner est une technique algorithmique consistant à diviser un problème de grande taille en plusieurs sous-problèmes. L'étape de subdivision est appliqué recursivement. Son nom est inspiré du proverbe « Diviser pour régner » (en latin : « Divide ut imperes »)
Sommaire |
[modifier] Présentation
Les algorithmes récursifs utilisent naturellement cette technique : ils s'appellent eux-mêmes une ou plusieurs fois sur une partition du problème initial et combinent les solutions pour retrouver une solution au problème initial.
Exemple d'algorithme récursif : le « tri par fusion »
La donnée initiale est une séquence d'entiers non triée. Le résultat est une séquence triée des mêmes entiers.
Ici,
- on divise la séquence de n éléments à trier en deux sous-séquences de n/2 éléments,
- on trie les deux sous-séquences à l'aide du tri par fusion (appel récursif),
- on combine, en les fusionnant, les deux sous-séquences triées pour produire la séquence triée.
La récursivité prend fin quand pour un appel à l'algorithme, la séquence à trier est de taille 1. Dans ce cas il n'y a rien à faire car par définition une telle séquence est déjà triée.
[modifier] Complexité
La complexité est ici considérée dans un cas particulier idéalisé:
Soit un problème P de taille N et un algorithme alpha s'exécutant en un temps T(alpha(N)) = O(N²) que l'on notera A(N), Notons aussi D(N) le temps pour diviser le problème P de taille N et C(N) le temps pour fusionner (Conquérir).
On subdivise le problème en deux parties égales, on applique alpha sur ces deux partitions pour les résoudre puis on fusionne les deux solutions pour obtenir une solution du problème P. Ceci correspond a un algorithme diviser pour régner avec une profondeur de récursion de 1. La complexité est maintenant:
2 * A(N / 2) + D(N) + C(N) = 1 / 2N2 + D(N) + C(N) (1)
Donc si D(N) + C(N) < 1 / 2N2 notre nouvel algorithme est plus performant.
Si on continue d'appliquer récursivement diviser pour régner sur les subdivisions du problème P on obtient:
(2)
Dans la pratique D(N) est souvent une constante O(1) et C(N) est linéaire en N. (2) se simplifie donc:
par conséquent la complexité asymptotique:
NlogN
[modifier] Exemples d'implémentation
- l'algorithme de tri « Tri rapide » ;
[modifier] Lien externe
 |
Portail de l'informatique – Accédez aux articles de Wikipédia concernant l’informatique. |
