Le paradigme « diviser pour régner » consiste à diviser un problème en plusieurs sous-problèmes indépendants, puis à les résoudre récursivement.

Ramener la résolution d'un problème dépendant d'un entier à la résolution d'un ou de plusieurs sous-problèmes indépendants

Réduire la taille du problème d'une unité à chaque appel récursif

Augmenter la complexité du problème à chaque appel récursif

Ignorer les sous-problèmes indépendants

Quel est le principe du paradigme « diviser pour régner » ?

Dans un algorithme conçu selon le paradigme « diviser pour régner », la taille du problème est divisée à chaque appel récursif, ce qui permet de résoudre des sous-problèmes indépendants.

La taille du problème est doublée à chaque appel récursif.

La taille du problème est divisée à chaque appel récursif.

La taille du problème reste constante à chaque appel récursif.

La taille du problème est réduite d'une unité à chaque appel récursif.

Qu'est-ce qui caractérise un algorithme conçu selon le paradigme « diviser pour régner » ?

La relation de récurrence caractéristique des algorithmes utilisant le paradigme « diviser pour régner » est souvent la forme T(n) = aT(n/b) + f(n), où a et b sont des constantes et f(n) représente le coût de traitement non récursif.

Quelle est la relation de récurrence caractéristique des algorithmes utilisant le paradigme « diviser pour régner » ?

Le tri fusion divise la liste en deux sous-listes, trie ces dernières récursivement, puis les fusionne dans l'ordre.

Il trie une liste en répartissant les éléments de cette dernière de manière aléatoire.

Il trie une liste en utilisant uniquement des boucles itératives.

Il trie une liste en la divisant en deux sous-listes, puis en fusionnant ces sous-listes triées.

Il trie une liste en permutant aléatoirement ses éléments jusqu'à obtenir un ordre croissant.

Comment fonctionne l'algorithme du tri fusion ?

La complexité temporelle du tri fusion est O(n log n), ce qui en fait l'un des algorithmes de tri les plus efficaces pour de grandes listes.