Mauvaise réponse !

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).

Mauvaise réponse !

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.

Mauvaise réponse !

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.

Bonne réponse !

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.

Mauvaise réponse !

L'algorithme de tri fusion, inventé en 1945 par John Von Neumann applique effectivement la méthode « diviser pour régner » pour fonctionner.

Mauvaise réponse !

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.

Bonne réponse !

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).