Principe

Définition

Diviser pour régner (divide and conquer), on dit aussi « diviser pour résoudre », fut une célèbre stratégie militaire avant de devenir une technique de conception algorithmique. Les généraux remarquèrent qu'il était plus facile de vaincre une armée de 50.000 hommes puis une autre de la même taille que de directement affronter une seule armée de 100.000 hommes.

Cette technique appliquée à l'informatique a souvent permis pour un problème donné de construire des algorithmes de plus basse complexité.

Diviser pour régner est une technique algorithmique consistant à diviser un problème de grande taille en plusieurs sous-problèmes analogues. L'étape de subdivision est appliquée récursivement[1].

Principe de diviser pour régner