Diviser pour Régner

Les algorithmes de type « diviser pour régner » (divide and conquer) consistent à :

1. partager le problème initial en plusieurs sous-problèmes indépendants « plus petits » que le problème initial ;

2. résoudre chaque sous-problème, récursivement lorsque le partage conduit à retrouver une version « réduite » du problème initial ;

3. combiner les solutions obtenues pour résoudre le problème initial.