Structures de données et algorithmes · Techniques

Diviser pour régner

Découper un problème en copies indépendantes plus petites de lui-même, résoudre chacune, puis combiner.

Commencer une leçon sur Diviser pour régner

À apprendre d'abord

• Tris diviser-pour-régner: Les tris diviser-pour-régner, tri fusion et tri rapide, qui battent le O(n carré) en découpant le problème.

Mène à

• Programmation dynamique: Résoudre un problème en mettant en cache les réponses à des sous-problèmes qui se chevauchent plutôt que de les recalculer.

Notions liées

• Recherche binaire: Diviser en deux, de façon répétée, une plage triée pour trouver une cible en temps logarithmique.
• Programmation dynamique: Résoudre un problème en mettant en cache les réponses à des sous-problèmes qui se chevauchent plutôt que de les recalculer.