Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel
Le paradigme « diviser pour régner » (divide and conquer) résout un problème en trois étapes : 1. Diviser : découper le problème en sous-problèmes plus petits de même nature. 2. Régner : résoudre chaque sous-problème, généralement par récursion. 3. Combiner : assembler les solutions partielles en une solution du problème global.
Deux exemples phares : - La recherche dichotomique dans un tableau trié : on compare la cible à l'élément du milieu et on élimine la moitié inutile à chaque étape. Complexité O(\log_2 n). - Le tri fusion : diviser le tableau en deux, trier récursivement chaque moitié, puis fusionner les deux moitiés triées. Complexité O(n \log n).
L'efficacité vient de la réduction rapide de la taille des sous-problèmes (souvent par moitié).
Recherche dichotomique : T(n) = O(\log_2 n), \qquad 2^{20} \approx 10^6.
Tri fusion : T(n) = O(n \log n) \quad (\log_2 n \text{ niveaux} \times O(n) \text{ par niveau}).
Recherche dichotomique itérative :
def recherche_dicho(tab, x): g, d = 0, len(tab) - 1 while g <= d: m = (g + d) // 2 if tab[m] == x: return m elif tab[m] < x: g = m + 1 else: d = m - 1 return -1
1. Vérifier la précondition (tableau trié pour la dichotomie). 2. Identifier les trois étapes : diviser, régner, combiner. 3. Pour la dichotomie, suivre l'évolution de l'intervalle [g, d]. 4. Justifier la complexité par le nombre de divisions (\log_2 n).
m + 1 / m - 1 : l'intervalle ne rétrécit plus.//) : indice non entier.La recherche dichotomique et le tri fusion sont les exemples attendus du paradigme. Sachez écrire la dichotomie en version itérative comme récursive, et savoir la dérouler à la main en suivant l'évolution des bornes g, du milieu m et de d. Justifiez les complexités O(\log n) et O(n \log n) par le découpage successif de la taille du problème. À l'épreuve pratique, on demande souvent de compléter la dichotomie ou la fonction de fusion de deux listes triées : soignez les conditions d'arrêt (g <= d), la mise à jour des bornes (m + 1, m - 1) et le calcul du milieu en division entière. Une erreur fréquente est d'oublier de garantir que l'intervalle rétrécit strictement, ce qui provoque une boucle infinie.