Diviser pour régner
Cours · NSI (terminale), chapitre 6 · terminale, spécialité numérique et sciences informatiques · le début du chapitre, la suite sur Adloun
La stratégie diviser pour régner (en anglais divide and conquer) est l'un des grands paradigmes de conception d'algorithmes. Plutôt que d'attaquer un problème de front, on le découpe en sous-problèmes plus petits, de même nature, que l'on résout indépendamment avant de recombiner leurs solutions. Cette idée, déjà présente dans la recherche dichotomique vue en classe de Première, conduit à des algorithmes particulièrement efficaces comme le tri fusion ou le tri rapide.
Dans ce chapitre, nous présentons le principe général, puis nous l'illustrons sur trois algorithmes classiques. Nous analysons leur complexité et nous les comparons aux approches naïves afin de mesurer le gain obtenu.
6.1 Le principe « diviser pour régner »
Un algorithme suit le paradigme diviser pour régner lorsqu'il résout un problème en trois étapes :
- Diviser : découper le problème en un ou plusieurs sous-problèmes de taille plus petite, de même nature ;
- Régner : résoudre chaque sous-problème, le plus souvent de manière récursive ; lorsque la taille devient suffisamment petite, on résout directement (cas de base) ;
- Combiner : assembler les solutions des sous-problèmes pour construire la solution du problème initial.
Méthode : Concevoir un algorithme « diviser pour régner »
Pour appliquer ce paradigme, on se pose systématiquement quatre questions :
- Quel est le cas de base (le plus petit cas, résolu sans récursion) ?
- Comment découper les données en sous-problèmes plus petits ?
- Comment combiner (fusionner) les sous-solutions ?
- La taille décroît-elle strictement à chaque appel, garantissant la terminaison ?
Le caractère récursif de ces algorithmes est essentiel : un problème de taille est ramené à des problèmes de taille (ou ), eux-mêmes ramenés à des problèmes encore plus petits, jusqu'à atteindre le cas de base.
Pour calculer , l'approche naïve effectue multiplications. En remarquant que si est pair, on divise l'exposant par deux à chaque étape.
def puissance(x, n):
if n == 0: # cas de base
return 1
demi = puissance(x, n // 2) # diviser + regner
if n % 2 == 0:
return demi * demi # combiner
else:
return demi * demi * xLe nombre de multiplications passe ainsi de à .
6.2 La recherche dichotomique
La recherche dichotomique permet de trouver un élément dans un tableau trié bien plus vite qu'une recherche séquentielle.
Soit tab un tableau trié par ordre croissant et cible une valeur recherchée. La recherche dichotomique consiste à comparer cible à l'élément du milieu :
- s'ils sont égaux, l'élément est trouvé ;
- si
cibleest plus petite, on poursuit dans la moitié gauche ; - sinon, on poursuit dans la moitié droite.
À chaque étape, la zone de recherche est divisée par deux : c'est bien une application du paradigme « diviser pour régner ».
def recherche_dichotomique(tab, cible):
g, d = 0, len(tab) - 1
while g <= d:
m = (g + d) // 2
if tab[m] == cible:
return m
elif tab[m] < cible:
g = m + 1
else:
d = m - 1
return -1 # cible absenteLa fonction renvoie l'indice de cible, ou si elle est absente.