La méthode « diviser pour régner » permet de traiter des problèmes complexes en les divisant en petits sous-problèmes plus simples à résoudre.
On commence par découper le problème en sous-problèmes (diviser), puis on résout les sous-problèmes (régner), et enfin on peu trouver la solution du problème inital à partir de ces solutions (combiner).
Comme son nom l'indique, la méthode « diviser pour régner » nécessite que le problème soit divisible en sous-problèmes pour pouvoir fonctionner.
La recherche dichotomique, ou binaire, consiste à séparer l'ensemble en deux parties, puis à vérifier si l'élément recherché se trouve dans l'une de ces moitiés. Si c'est le cas, on divise cette moitié par deux, sinon on regarde l'autre moitié, et ainsi de suite jusqu'à trouver l'élément.
Cette méthode a en effet besoin que les éléments soient triés, car elle se base sur leur ordre de classement pour en éliminer la moitié à chaque étape.
L'algorithme de tri fusion, inventé en 1945 par John Von Neumann applique effectivement la méthode « diviser pour régner » pour fonctionner.
Dans un tri fusion on va en effet commencer par diviser le problème en deux, puis on résout séparément chaque sous-problème, et enfin on combine les solutions.
Dans un tri fusion, il y a de l'ordre de log(n) étapes de division/combinaison, et chaque étape a un coût de l'ordre de n, donc le tri fusion possède une complexité de nlog(n).
8
Félicitations pour le score parfait !Encore un petit effort !
Retente ta chance, tu peux faire mieux.
Pour suivre tes progrès, crée ton compte Lumni, c’est gratuit !
Je crée mon compte
Joue à ce quiz et gagne facilement jusqu'à
80 Lumniz
en te connectant !
Il n’y a pas de Lumniz à gagner car tu as déjà vu ce contenu. Ne t’inquiète pas, il y a plein d’autres vidéos, jeux, quiz ou articles intéressants à explorer et toujours plus de Lumniz à remporter.
La méthode « diviser pour régner »
En informatique, il est parfois impossible de résoudre directement un problème, surtout lorsqu'il est trop long ou complexe. Ainsi, on peut alors être amené à utiliser différentes solutions, comme la méthode « diviser pour régner ». En quoi consiste cette méthode et quelles sont ses applications ?