Algorithme Diviser et Conquérir
Paradigme algorithmique très populaire, un algorithme typique Diviser et Conquérir résout un problème en utilisant les trois étapes suivantes :
- Diviser : Décomposer le problème donné en sous-problèmes de même type.
- Conquérir : Résoudre récursivement ces sous-problèmes
- Combiner : Combiner de manière appropriée les réponses
Les algorithmes suivants sont des algorithmes standard qui sont des algorithmes de type Diviser et Conquérir :
1 – La recherche binaire est un algorithme de recherche. À chaque étape, l’algorithme compare l’élément d’entrée x avec la valeur de l’élément central du tableau. Si les valeurs correspondent, il retourne l’indice du milieu. Sinon, si x est inférieur à l’élément du milieu, alors l’algorithme récure pour le côté gauche de l’élément du milieu, sinon récure pour le côté droit de l’élément du milieu.
2 – Quicksort est un algorithme de tri. L’algorithme choisit un élément pivot, réorganise les éléments du tableau de telle sorte que tous les éléments plus petits que l’élément pivot choisi se déplacent vers le côté gauche du pivot, et tous les éléments plus grands se déplacent vers le côté droit. Enfin, l’algorithme trie récursivement les sous-réseaux à gauche et à droite de l’élément pivot.
3 – Merge Sort est également un algorithme de tri. L’algorithme divise le tableau en deux moitiés, les trie récursivement et enfin fusionne les deux moitiés triées.
4 – Plus proche paire de points : Le problème consiste à trouver la paire de points la plus proche dans un ensemble de points dans le plan x-y. Le problème peut être résolu en O(n²) temps en calculant les distances de chaque paire de points et en comparant les distances pour trouver le minimum. L’algorithme Diviser et Conquérir résout le problème en O(nLogn) temps.
5 – L’algorithme de Strassen est un algorithme efficace pour multiplier deux matrices. Une méthode simple pour multiplier deux matrices nécessite 3 boucles imbriquées et est en O(n³). L’algorithme de Strassen multiplie deux matrices en O(n².8974) temps.
6 – L’algorithme de la transformée de Fourier rapide (FFT) de Cooley-Tukey est l’algorithme le plus courant pour la FFT. C’est un algorithme de type diviser pour régner qui fonctionne en O(nlogn) temps.
7 – Algorithme de Karatsuba pour la multiplication rapide : Il effectue la multiplication de deux nombres à n chiffres en au plus 3n^(log 3) multiplications à un chiffre en général (et exactement n^(log3) lorsque n est une puissance de 2). Il est donc plus rapide que l’algorithme classique, qui nécessite n² produits à un chiffre.
Problème du comptage des inversions
Nous allons considérer un problème qui se pose dans l’analyse des classements, qui deviennent importants pour un certain nombre d’applications actuelles. Par exemple, un certain nombre de sites sur le Web utilisent une technique connue sous le nom de filtrage collaboratif, dans laquelle ils essaient de faire correspondre vos préférences (pour les livres, les films, les restaurants) avec celles d’autres personnes sur Internet. Une fois que le site Web a identifié les personnes ayant des goûts « similaires » aux vôtres – sur la base d’une comparaison de la façon dont vous et eux évaluez diverses choses – il peut recommander de nouvelles choses que ces autres personnes ont aimées. Une autre application apparaît dans les outils de recta-recherche sur le Web, qui exécutent la même requête sur de nombreux moteurs de recherche différents et tentent ensuite de synthétiser les résultats en recherchant les similitudes et les différences entre les divers classements que les moteurs de recherche renvoient.
Une question centrale dans les applications de ce type est le problème de la comparaison de deux classements. Vous classez un ensemble de films rt, puis un système de filtrage collaboratif consulte sa base de données pour rechercher d’autres personnes qui ont eu des classements « similaires ». Mais quel est le bon moyen de mesurer, numériquement, la similarité des classements de deux personnes ? Il est clair qu’un classement identique est très similaire, et qu’un classement complètement inversé est très différent ; nous voulons quelque chose qui interpole par la région intermédiaire.
Envisageons de comparer votre classement et le classement d’un étranger sur le même ensemble de n films. Une méthode naturelle serait d’étiqueter les films de 1 à n selon votre classement, puis d’ordonner ces étiquettes selon le classement de l’étranger, et de voir combien de paires sont « hors d’ordre ». Plus concrètement, nous allons considérer le problème suivant. On nous donne une séquence de n nombres a1, …, an ; nous supposerons que tous les nombres sont distincts. Nous voulons définir une mesure qui nous indique à quel point cette liste est loin d’être en ordre croissant ; la valeur de la mesure devrait être 0 si a1 < a2 << an, et devrait augmenter à mesure que les nombres deviennent plus brouillés.
Une façon naturelle de quantifier cette notion est de compter le nombre d’inversions. On dit que deux indices i < j forment une inversion si ai > aj, c’est-à-dire si les deux éléments ai et aj sont » hors d’ordre « . Nous chercherons à déterminer le nombre d’inversions dans la suite a1, …, an.
.