Dans ce didacticiel, vous apprendrez comment fonctionne l'algorithme de division et de conquête. Nous comparerons également l'approche diviser pour conquérir par rapport à d'autres approches pour résoudre un problème récursif.
Un algorithme de division et de conquête est une stratégie de résolution d'un gros problème en
- décomposer le problème en sous-problèmes plus petits
- résoudre les sous-problèmes, et
- en les combinant pour obtenir le résultat souhaité.
Pour utiliser l'algorithme de division et de conquête, la récursivité est utilisée. En savoir plus sur la récursivité dans différents langages de programmation:
- Récursivité en Java
- Récursivité en Python
- Récursivité en C ++
Comment fonctionnent les algorithmes Divide and Conquer?
Voici les étapes impliquées:
- Divide : divise le problème donné en sous-problèmes en utilisant la récursivité.
- Conquérir : Résolvez les petits sous-problèmes de manière récursive. Si le sous-problème est suffisamment petit, résolvez-le directement.
- Combiner: Combinez les solutions des sous-problèmes qui font partie du processus récursif pour résoudre le problème réel.
Comprenons ce concept à l'aide d'un exemple.
Ici, nous allons trier un tableau en utilisant l'approche de division et de conquête (c.-à-d. Tri par fusion).
- Soit le tableau donné:
Tableau pour le tri par fusion - Divisez le tableau en deux moitiés.
Divisez le tableau en deux sous-parties
Encore une fois, divisez chaque sous-partie de manière récursive en deux moitiés jusqu'à ce que vous obteniez des éléments individuels.
Divisez le tableau en sous-parties plus petites - Maintenant, combinez les éléments individuels de manière triée. Ici, conquérir et combiner les étapes se côtoient.
Combinez les sous-parties
Complexité temporelle
La complexité de l'algorithme de division et de conquête est calculée à l'aide du théorème maître.
T (n) = aT (n / b) + f (n), où, n = taille de l'entrée a = nombre de sous-problèmes dans la récursivité n / b = taille de chaque sous-problème. Tous les sous-problèmes sont supposés avoir la même taille. f (n) = coût du travail effectué en dehors de l'appel récursif, qui comprend le coût de la division du problème et le coût de la fusion des solutions
Prenons un exemple pour trouver la complexité temporelle d'un problème récursif.
Pour un tri par fusion, l'équation peut être écrite comme suit:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Où, a = 2 (à chaque fois, un problème est divisé en 2 sous-problèmes) n / b = n / 2 (la taille de chaque sous-problème correspond à la moitié de l'entrée) f (n) = temps nécessaire pour diviser le problème et fusionner les sous-problèmes T (n / 2) = O (n log n) le théorème maître.) Maintenant, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Approche Divide and Conquer Vs Dynamic
L'approche diviser pour vaincre divise un problème en sous-problèmes plus petits; ces sous-problèmes sont en outre résolus de manière récursive. Le résultat de chaque sous-problème n'est pas stocké pour référence future, alors que, dans une approche dynamique, le résultat de chaque sous-problème est stocké pour référence future.
Utilisez l'approche de division et de conquête lorsque le même sous-problème n'est pas résolu plusieurs fois. Utilisez l'approche dynamique lorsque le résultat d'un sous-problème doit être utilisé plusieurs fois dans le futur.
Comprenons cela avec un exemple. Supposons que nous essayions de trouver la série de Fibonacci. Ensuite,
Approche Divide and Conquer:
fib (n) Si n <2, retourne 1 Sinon, renvoie f (n - 1) + f (n -2)
Approche dynamique:
mem = () fib (n) Si n dans mem: retourne mem (n) sinon, Si n <2, f = 1 sinon, f = f (n - 1) + f (n -2) mem (n) = f retour f
Dans une approche dynamique, mem stocke le résultat de chaque sous-problème.
Avantages de l'algorithme Divide and Conquer
- La complexité pour la multiplication de deux matrices en utilisant la méthode naïve est O (n 3 ), alors que l'utilisation de l'approche diviser et conquérir (c'est-à-dire la multiplication matricielle de Strassen) est O (n 2.8074 ). Cette approche simplifie également d'autres problèmes, tels que la tour de Hanoi.
- Cette approche convient aux systèmes multiprocesseurs.
- Il utilise efficacement les caches de mémoire.
Diviser et conquérir les applications
- Recherche binaire
- Tri par fusion
- Tri rapide
- Multiplication de la matrice de Strassen
- Algorithme de Karatsuba
