Diviser pour régner

Le diviser pour régner est un paradigme de conception d'algorithmes qui résout un problème en le décomposant en sous-problèmes plus petits de même type, en les résolvant de manière récursive, puis en combinant leurs solutions pour obtenir une solution au problème original.

Definition

Un algorithme de diviser pour régner décompose récursivement un problème en deux ou plusieurs sous-problèmes de même type ou de types apparentés jusqu'à ce que les sous-problèmes soient suffisamment simples pour être résolus directement, puis combine les solutions des sous-problèmes pour produire la réponse au problème original.

Scope

Ce sujet couvre la structure en trois étapes des algorithmes de diviser pour régner (diviser, conquérir, combiner), des exemples canoniques tels que le tri fusion (mergesort), le tri rapide (quicksort), la recherche binaire et la multiplication rapide d'entiers et de matrices, ainsi que l'analyse de leurs temps d'exécution basée sur les récurrences. Il est étroitement lié au théorème maître et aux techniques de résolution de récurrences utilisées pour analyser de tels algorithmes.

Core questions

• Comment un problème est-il décomposé de manière à ce que les sous-problèmes soient indépendants et de même forme ?
• Quel travail est effectué à l'étape de combinaison, et comment cela affecte-t-il le coût total ?
• Comment les récurrences résultantes sont-elles résolues pour obtenir des temps d'exécution asymptotiques ?
• Quand le diviser pour régner surpasse-t-il une approche itérative directe ?

Key concepts

• diviser, conquérir, combiner
• relations de récurrence
• théorème maître
• mergesort
• quicksort
• recherche binaire
• multiplication de Karatsuba
• multiplication matricielle de Strassen

Key theories

Théorème maître pour les récurrences

Le théorème maître fournit des solutions asymptotiques sous forme close pour les récurrences de type diviser pour régner de la forme T(n) = aT(n/b) + f(n) en comparant le coût des sous-problèmes récursifs au coût de combinaison f(n).

Multiplication sous-quadratique par décomposition

La division récursive des opérandes et la réduction du nombre de multiplications récursives (comme dans la multiplication de Karatsuba et la multiplication matricielle de Strassen) produisent des algorithmes asymptotiquement plus rapides que les méthodes quadratiques et cubiques naïves.

Clinical relevance

Le diviser pour régner est à la base de nombreux algorithmes parmi les plus largement déployés : le tri efficace (mergesort, quicksort) dans les bibliothèques standard, la recherche binaire dans les routines de recherche, la Transformation de Fourier Rapide (Fast Fourier Transform) dans le traitement du signal et de l'image, et la multiplication rapide utilisée en cryptographie et en arithmétique à précision arbitraire.

History

Le tri fusion (Mergesort) est attribué à John von Neumann (1945). C. A. R. Hoare a publié le tri rapide (quicksort) en 1962. La multiplication sous-quadratique de Karatsuba en 1960 et l'algorithme de multiplication matricielle de Strassen en 1969 ont démontré que la décomposition récursive pouvait dépasser les bornes classiques, contribuant ainsi à établir le diviser pour régner comme un paradigme fondamental.

Key figures

• C. A. R. Hoare
• John von Neumann
• Anatoly Karatsuba
• Volker Strassen

Seminal works

• hoare1962
• cormen2009

Frequently asked questions

Pourquoi le tri fusion est-il en O(n log n) ?

Le tri fusion divise le tableau en deux moitiés (log n niveaux de récursion) et à chaque niveau effectue une fusion en temps linéaire sur tous les éléments, donnant la récurrence T(n) = 2T(n/2) + O(n), que le théorème maître résout comme O(n log n).

Le tri rapide est-il un algorithme de diviser pour régner même s'il n'a pas d'étape de combinaison explicite ?

Oui. Le tri rapide effectue son travail principal à l'étape de division via le partitionnement autour d'un pivot ; une fois les deux partitions triées récursivement, aucun travail de combinaison n'est nécessaire. Le paradigme permet que l'essentiel de l'effort se situe dans l'une des trois phases.