Diviser pour régner


Dans ce chapitre, nous allons étudier certains algorithmes dont la philosophie de fonctionnement se rapproche de ladage “diviser pour régner” . Lidée est de décomposer un problème en plusieurs sous-problèmes, que lon résoudra suivant le même principe. Il ne reste plus alors quà combiner les résultats des sous-problèmes pour obtenir la réponse recherchée.

Nous reviendrons dans un premier temps sur la recherche dichotomique normalement déjà étudiée en Première, puis nous la réexaminerons en utilisant la récursivité étudiée en Terminale.

Dans un second temps, nous découvrirons un nouvel algorithme de tri appelé le tri fusion. Cet algorithme est un exemple parfait du principe “diviser pour régner”. Par rapport aux algorithmes de tri par insertion ou par sélection étudiés en Première, son efficacité est bien meilleure: elle est même optimale !