Ce qu’il faut savoir

Le diviser pour régner (Divide and conquer en anglais) est une méthode algorithmique basée sur le principe suivant :

On prend un problème (généralement complexe à résoudre), on divise ce problème en une multitude de petits problèmes, l'idée étant que les "petits problèmes" seront plus simples à résoudre que le problème original. Une fois les petits problèmes résolus, on recombine les "petits problèmes résolus" afin d'obtenir la solution du problème de départ. Le paradigme "diviser pour régner" repose donc sur 3 étapes :

• DIVISER : le problème d'origine est divisé en un certain nombre de sous-problèmes
• RÉGNER : on résout les sous-problèmes (les sous-problèmes sont plus faciles à résoudre que le problème d'origine)
• COMBINER : les solutions des sous-problèmes sont combinées afin d'obtenir la solution du problème d'origine.

Exemple d’algorithme basé sur la méthode diviser pour régner : le tri-fusion (vous devez connaître le principe de cet algorithme).

L’algorithme de tri-fusion a une complexité en O(nlog₂(n))

Ce qu’il faut savoir faire

être capable d’implémenter l’algorithme de tri-fusion en Python