Publié · en amélioration
Algorithm
Diviser pour régner découpe un problème en sous-problèmes plus petits, les résout récursivement et combine les résultats, comme le tri fusion.
Diviser pour régner est une technique de conception d'algorithmes : on découpe un problème en instances plus petites du même problème (diviser), on les résout récursivement (régner), puis on construit la réponse finale à partir de leurs résultats (combiner). Le tri fusion, la recherche dichotomique, l'exponentiation rapide, quickselect, la multiplication de Karatsuba et la recherche de la paire de points la plus proche suivent ce schéma.
Cette approche compte parce qu'elle transforme souvent une solution naïve en O(n^2) en O(n log n), voire O(log n). L'idée clé, calculer pendant l'étape de combinaison l'information qui traverse la coupure, comme pour le comptage des inversions, revient sans cesse en entretien technique, et les mêmes idées font tourner les bibliothèques de tri, la multiplication de grands nombres, la FFT et l'exponentiation modulaire en cryptographie.
Commencez par dérouler le tri fusion à la main pour bien saisir diviser, régner et combiner, puis entraînez-vous à poser des récurrences comme T(n) = aT(n/b) + f(n) et à les résoudre avec le théorème maître. Implémentez ensuite vous-même le comptage des inversions, l'exponentiation rapide et quickselect, et apprenez à reconnaître quand des sous-problèmes qui se chevauchent demandent plutôt la programmation dynamique.
Diviser l'entrée, résoudre les parties récursivement et combiner les réponses. Un cas de base arrête la récursion, et le coût de la combinaison détermine généralement le temps d'exécution.
On écrit le temps d'exécution T(n) = aT(n/b) + f(n) et on compare f(n) à n^(log_b a) pour obtenir par exemple O(n log n) pour le tri fusion.
Traiter en temps linéaire les cas qui chevauchent les deux moitiés, comme pour le comptage des inversions ou le sous-tableau maximal, est l'idée centrale.
En ne gardant qu'un seul sous-problème, comme la recherche dichotomique, l'exponentiation rapide et quickselect, on obtient des algorithmes en O(log n) ou en O(n) en moyenne.
sort_count trie la liste par tri fusion et, chaque fois qu'un élément de la moitié droite passe en premier, ajoute le nombre d'éléments qui attendent encore à gauche : les inversions sont ainsi comptées en O(n log n). power est l'exponentiation rapide : elle divise l'exposant par deux et élève au carré, ce qui ne demande que O(log e) multiplications. python divide_and_conquer.py affiche la liste triée avec ses 14 inversions et 3^200 modulo 1 000 000 007.
divide_and_conquer.py
def sort_count(a):
"""Return (sorted list, number of inversions) using merge sort."""
if len(a) <= 1:
return list(a), 0
mid = len(a) // 2
left, x = sort_count(a[:mid])
right, y = sort_count(a[mid:])
merged, i, j, cross = [], 0, 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
cross += len(left) - i # right[j] is smaller than every left[i:]
merged += left[i:] + right[j:]
return merged, x + y + cross
def power(base, exp, mod):
"""base ** exp % mod with O(log exp) multiplications."""
if exp == 0:
return 1 % mod
half = power(base, exp // 2, mod)
result = half * half % mod
return result * base % mod if exp % 2 else result
if __name__ == "__main__":
print(sort_count([5, 2, 4, 7, 1, 3, 2, 6])) # ([1, 2, 2, 3, 4, 5, 6, 7], 14)
print(power(3, 200, 1_000_000_007)) # 136318165
python divide_and_conquer.pySix chapitres pour aller de l'installation aux notions essentielles de Diviser pour régner.
Posez vos questions, partagez votre expérience et échangez vos avis sur Diviser pour régner.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.