Modèle diviser pour régner
Extrayez de merge sort le modèle en trois étapes (diviser, résoudre, combiner), puis appliquez-le systématiquement à de nouvelles formes de problèmes.
Modèle diviser pour régner est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu’est-ce que le paradigme diviser pour régner ?
Le paradigme diviser pour régner (D&C) résout un problème en le décomposant en sous-problèmes indépendants du même type, en résolvant chacun récursivement, puis en combinant leurs solutions. Le mot clé est indépendants : les sous-problèmes ne partagent pas d’état, contrairement à la programmation dynamique, où ils se chevauchent. Exemples classiques : le tri par fusion, la recherche binaire, le tri rapide, la paire de points la plus proche et la multiplication rapide de matrices. Le paradigme diviser pour régner atteint généralement un temps O(n log n) grâce à ce modèle en trois étapes.
# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP: sub-problems OVERLAP (same sub-problem solved multiple times)
# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing
# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n) [merge sort]
# T(n) = T(n/2) + O(1) → O(log n) [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]Le modèle en trois étapes
Tout algorithme diviser pour régner suit trois étapes : (1) Diviser — séparer le problème en deux sous-problèmes plus petits ou davantage, généralement au milieu. (2) Résoudre — résoudre récursivement chaque sous-problème. Définir un cas de base pour arrêter la récursion, généralement n ≤ 1. (3) Combiner — fusionner ou combiner les solutions des sous-problèmes pour obtenir la solution globale. Toute la créativité réside dans l’étape Combiner ; Diviser consiste généralement simplement à séparer le problème au milieu.
def divide_and_conquer(arr, lo, hi):
# BASE CASE: trivial sub-problem
if lo >= hi:
return base_case_result(arr, lo, hi)
# DIVIDE: split at midpoint
mid = (lo + hi) // 2
# CONQUER: solve sub-problems recursively
left_result = divide_and_conquer(arr, lo, mid)
right_result = divide_and_conquer(arr, mid + 1, hi)
# COMBINE: merge results
return combine(left_result, right_result, arr, lo, mid, hi)
def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)Le tri par fusion comme exemple canonique
Le tri par fusion illustre parfaitement le paradigme diviser pour régner : Diviser le tableau au milieu. Résoudre en triant récursivement chaque moitié. Combiner en fusionnant les deux moitiés triées en O(n). C’est lors de l’étape de fusion que s’effectue tout le travail. Récurrence : T(n) = 2T(n/2) + O(n). D’après le cas 2 du théorème maître : T(n) = O(n log n). C’est la récurrence diviser pour régner la plus importante à mémoriser.
def merge_sort(arr):
# BASE CASE
if len(arr) <= 1:
return arr
# DIVIDE
mid = len(arr) // 2
# CONQUER
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# COMBINE
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]
print(merge_sort([5, 3, 8, 1, 9, 2])) # [1,2,3,5,8,9]Référence rapide du théorème maître
Le théorème maître résout les récurrences de la forme T(n) = aT(n/b) + f(n) : Cas 1 : f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a)). Cas 2 : f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n). Cas 3 : f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n)). Pour le tri par fusion : a=2, b=2, f(n)=O(n), n^log_2(2)=n → cas 2 → O(n log n).
# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n) → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1) → a=2,b=2,f=1,n^1=n >> 1 → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2) → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1) → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree
recurrences = [
('Merge sort: 2T(n/2)+n', 'O(n log n)'),
('Binary search: T(n/2)+1', 'O(log n)'),
('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)Sous-tableau maximal : approche diviser pour régner
Avec l’approche diviser pour régner appliquée au sous-tableau maximal, la réponse se trouve soit entièrement dans la moitié gauche, soit entièrement dans la moitié droite, soit de part et d’autre du milieu. Pour le cas qui traverse le milieu, on étend la recherche vers la gauche à partir de mid et vers la droite à partir de mid+1, en prenant la somme maximale dans chaque direction, puis on combine les résultats. Cette approche diviser pour régner en O(n log n) est plus lente que l’algorithme de Kadane en O(n), mais elle illustre parfaitement le modèle et constitue une question d’entretien courante sur le paradigme diviser pour régner.
def max_subarray_dc(nums, lo=None, hi=None):
if lo is None: lo, hi = 0, len(nums) - 1
if lo == hi: return nums[lo]
mid = (lo + hi) // 2
# Conquer
left_max = max_subarray_dc(nums, lo, mid)
right_max = max_subarray_dc(nums, mid + 1, hi)
# Cross-midpoint sum
left_sum = curr = 0
for i in range(mid, lo - 1, -1):
curr += nums[i]
left_sum = max(left_sum, curr)
right_sum = curr = 0
for i in range(mid + 1, hi + 1):
curr += nums[i]
right_sum = max(right_sum, curr)
cross_max = left_sum + right_sum
return max(left_max, right_max, cross_max)
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums)) # 6Fonction puissance : exponentiation rapide
Exponentiation rapide (LeetCode 50) : calculer x^n en O(log n) à l’aide du paradigme diviser pour régner. Si n est pair : x^n = (x^(n/2))^2. Si n est impair : x^n = x × x^(n-1). Traiter les valeurs négatives de n avec x^(-n) = 1/x^n. Chaque appel récursif divise n par deux, donc la profondeur est O(log n). C’est un exemple simple où l’étape Combiner consiste uniquement en une multiplication : c’est élémentaire, mais efficace.
def my_pow(x, n):
if n < 0:
return 1 / my_pow(x, -n)
# BASE CASE
if n == 0: return 1
# DIVIDE and CONQUER
half = my_pow(x, n // 2)
if n % 2 == 0:
return half * half # even: x^n = (x^(n/2))^2
else:
return x * half * half # odd: x^n = x * (x^(n/2))^2
print(my_pow(2, 10)) # 1024
print(my_pow(2, -2)) # 0.25
print(my_pow(3, 5)) # 243
print(my_pow(0, 0)) # 1Tableau trié vers un BST
Convertir un tableau trié en BST (LeetCode 108) utilise le paradigme diviser pour régner : prendre le milieu comme racine afin de garantir l’équilibre de la hauteur, puis construire récursivement le sous-arbre gauche à partir de la moitié gauche et le sous-arbre droit à partir de la moitié droite. On obtient ainsi un BST équilibré en hauteur, de hauteur minimale O(log n). La structure diviser pour régner reprend celle de la recherche binaire : à chaque niveau de récursion, le milieu devient la racine de la sous-plage courante.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sorted_array_to_bst(nums):
def helper(lo, hi):
if lo > hi: return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid]) # DIVIDE at midpoint
node.left = helper(lo, mid - 1) # CONQUER left
node.right = helper(mid + 1, hi) # CONQUER right
# COMBINE: already done by assignment
return node
return helper(0, len(nums) - 1)
def inorder(node):
if not node: return []
return inorder(node.left) + [node.val] + inorder(node.right)
root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root)) # [-10,-3,0,5,9] (sorted, proving BST property)Quand diviser pour régner n’est pas le meilleur choix
Le paradigme diviser pour régner entraîne des coûts supplémentaires : profondeur de la pile d’appels de fonctions, découpage du tableau en tranches si l’on n’utilise pas d’indices, et étape de combinaison. Il est optimal lorsque l’étape de combinaison coûte O(n) ou moins. Lorsque les sous-problèmes se chevauchent, le paradigme diviser pour régner recalcule inutilement les solutions : la programmation dynamique est alors nécessaire. Lorsque l’étape de combinaison domine, par exemple en O(n²), diviser pour régner n’améliore pas les approches naïves. Il faut savoir choisir : diviser pour régner pour les sous-problèmes indépendants, DP pour les sous-problèmes qui se chevauchent.
# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead
def fib_dc(n):
if n <= 1: return n
return fib_dc(n-1) + fib_dc(n-2) # O(2^n)!
def fib_dp(n):
a, b = 0, 1
for _ in range(n): a, b = b, a+b
return a # O(n)
print(fib_dp(30)) # fast
# fib_dc(40) would take seconds — do not run large values!Diviser pour régner appliqué à la recherche binaire dans une matrice triée
La recherche dans une matrice à deux dimensions (LeetCode 240), dont chaque ligne et chaque colonne sont triées, peut être résolue par une approche diviser pour régner : commencer dans le coin supérieur droit. Si la valeur actuelle > la cible, se déplacer vers la gauche, ce qui élimine une colonne. Si la valeur actuelle < la cible, descendre, ce qui élimine une ligne. Si elles sont égales, l’élément est trouvé. Cet algorithme en O(m+n) n’est techniquement pas récursif, mais il partage l’idée clé suivante : éliminer la moitié de l’espace de recherche à chaque étape.
def search_matrix(matrix, target):
if not matrix: return False
m, n = len(matrix), len(matrix[0])
row, col = 0, n - 1 # start top-right
while row < m and col >= 0:
val = matrix[row][col]
if val == target:
return True
elif val > target:
col -= 1 # eliminate this column
else:
row += 1 # eliminate this row
return False
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5)) # True
print(search_matrix(matrix, 20)) # FalseAnalyse par arbre de récursion
Pour les récurrences diviser pour régner qui ne correspondent pas au théorème maître, utilisez la méthode de l’arbre de récursion. Représentez chaque niveau des appels récursifs et additionnez le travail effectué à chaque niveau. Pour le tri par fusion, au niveau k, il y a 2^k sous-problèmes de taille n/2^k. Travail par niveau = 2^k × O(n/2^k) = O(n). Nombre total de niveaux = log n. Travail total = O(n log n). Cette méthode visuelle fonctionne pour toute récurrence et permet de comprendre pourquoi diviser pour régner atteint généralement O(n log n).
# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)
import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')Présenter diviser pour régner en entretien
Lorsque vous présentez une solution diviser pour régner en entretien : (1) énoncez explicitement les trois étapes : « Je vais diviser le problème au milieu, résoudre récursivement chaque moitié, puis combiner les résultats par fusion. » (2) identifiez clairement le cas de base ; (3) établissez la récurrence : T(n) = 2T(n/2) + O(n) ; (4) appliquez le théorème maître ou l’arbre de récursion pour obtenir O(n log n) ; (5) indiquez dans quels cas diviser pour régner est préférable ou moins efficace que les autres solutions, comme DP pour les sous-problèmes qui se chevauchent ou l’algorithme de Kadane pour le sous-tableau maximal.
# D&C interview template to memorize:
def dc_template(problem, lo, hi):
# 1. BASE CASE (state it first)
if lo == hi: return solve_base(problem, lo)
# 2. DIVIDE
mid = (lo + hi) // 2
# 3. CONQUER
left = dc_template(problem, lo, mid)
right = dc_template(problem, mid + 1, hi)
# 4. COMBINE (this is where the algorithm-specific logic goes)
return combine_results(left, right, problem, lo, mid, hi)
def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)
print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')Vérification rapide
Testez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation — présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que le paradigme diviser pour régner suit le modèle : cas de base → division au milieu → résolution récursive → combinaison, que T(n) = 2T(n/2) + O(n) donne O(n log n) selon le cas 2 du théorème maître, et que diviser pour régner est optimal pour les sous-problèmes indépendants, tandis que DP est nécessaire lorsque les sous-problèmes se chevauchent. Nous allons maintenant appliquer diviser pour régner au comptage des inversions dans un tableau à l’aide d’une variante du tri par fusion.
Questions Fréquemment Posées
La leçon « Modèle diviser pour régner » est-elle gratuite ?
Oui — le texte complet de « Modèle diviser pour régner » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Modèle diviser pour régner » ?
Extrayez de merge sort le modèle en trois étapes (diviser, résoudre, combiner), puis appliquez-le systématiquement à de nouvelles formes de problèmes. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Modèle diviser pour régner » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Modèle diviser pour régner
- Compter les inversions avec un tri fusion modifié
- Élément majoritaire : vote de Boyer-Moore
- Médiane de deux tableaux triés