ULUMINE · Numérique et sciences informatiques (NSI) · Terminale
La méthode « diviser pour régner »
Diviser pour régner : découper un problème en sous-problèmes semblables plus petits, les résoudre récursivement, puis combiner.
Méthode
- Diviser, régner (récursivement), combiner.
- Environ log₂(n) niveaux de découpage quand on divise par 2.
Exemples
- Dichotomie (liste triée) : environ log₂(n) étapes.
- Tri fusion : n log₂(n) ; fusion de p et q éléments : au plus p + q − 1 comparaisons.
- Exponentiation rapide, rotation d’image, maximum.
Pièges à éviter
- Appliquer la dichotomie à une liste non triée.
- Mal découper (oublier ou répéter l’élément du milieu).
- Oublier le cas de base, ou en écrire un qui laisse une liste de même taille.
- Croire que le tri fusion ne consomme pas de mémoire supplémentaire.