In diesem Tutorial erfahren Sie, wie der Divide and Conquer-Algorithmus funktioniert. Wir werden auch den Divide and Conquer-Ansatz mit anderen Ansätzen zur Lösung eines rekursiven Problems vergleichen.
Ein Divide and Conquer-Algorithmus ist eine Strategie zur Lösung eines großen Problems durch
- Aufteilen des Problems in kleinere Unterprobleme
- Lösen der Unterprobleme und
- Kombinieren Sie sie, um die gewünschte Ausgabe zu erhalten.
Um den Divide and Conquer-Algorithmus zu verwenden, wird die Rekursion verwendet. Erfahren Sie mehr über Rekursion in verschiedenen Programmiersprachen:
- Rekursion in Java
- Rekursion in Python
- Rekursion in C ++
Wie funktionieren Divide and Conquer-Algorithmen?
Hier sind die Schritte:
- Teilen : Teilen Sie das gegebene Problem mithilfe von Rekursion in Unterprobleme.
- Erobern : Lösen Sie die kleineren Unterprobleme rekursiv. Wenn das Teilproblem klein genug ist, lösen Sie es direkt.
- Kombinieren: Kombinieren Sie die Lösungen der Teilprobleme, die Teil des rekursiven Prozesses sind, um das eigentliche Problem zu lösen.
Lassen Sie uns dieses Konzept anhand eines Beispiels verstehen.
Hier sortieren wir ein Array nach dem Divide and Conquer-Ansatz (dh Merge Sort).
- Das angegebene Array sei:
Array für die Zusammenführungssortierung - Teilen Sie das Array in zwei Hälften.
Teilen Sie das Array in zwei Unterteile
. Teilen Sie jedes Unterteil rekursiv in zwei Hälften, bis Sie einzelne Elemente erhalten.
Teilen Sie das Array in kleinere Unterteile - Kombinieren Sie nun die einzelnen Elemente sortiert. Hier erobern und kombinieren Sie Schritte nebeneinander.
Kombinieren Sie die Unterteile
Zeitliche Komplexität
Die Komplexität des Divide and Conquer-Algorithmus wird nach dem Master-Theorem berechnet.
T (n) = aT (n / b) + f (n), wobei n = Größe der Eingabe a = Anzahl der Teilprobleme in der Rekursion n / b = Größe jedes Teilproblems. Es wird angenommen, dass alle Teilprobleme die gleiche Größe haben. f (n) = Kosten der außerhalb des rekursiven Aufrufs geleisteten Arbeit, einschließlich der Kosten für die Aufteilung des Problems und der Kosten für die Zusammenführung der Lösungen
Nehmen wir ein Beispiel, um die zeitliche Komplexität eines rekursiven Problems zu ermitteln.
Für eine Zusammenführungssortierung kann die Gleichung wie folgt geschrieben werden:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Wobei a = 2 (jedes Mal wird ein Problem in 2 Teilprobleme unterteilt) n / b = n / 2 (Größe jedes Unterproblems ist die Hälfte der Eingabe) f (n) = Zeit, die benötigt wird, um das Problem zu teilen und die Unterprobleme zusammenzuführen T (n / 2) = O (n log n) (Um dies zu verstehen, lesen Sie bitte der Hauptsatz.) Nun ist T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Teilen und Erobern gegen dynamischen Ansatz
Der Divide and Conquer-Ansatz unterteilt ein Problem in kleinere Teilprobleme. Diese Teilprobleme werden rekursiv weiter gelöst. Das Ergebnis jedes Teilproblems wird nicht zur zukünftigen Bezugnahme gespeichert, wohingegen bei einem dynamischen Ansatz das Ergebnis jedes Teilproblems zur zukünftigen Bezugnahme gespeichert wird.
Verwenden Sie den Divide and Conquer-Ansatz, wenn dasselbe Teilproblem nicht mehrmals gelöst wird. Verwenden Sie den dynamischen Ansatz, wenn das Ergebnis eines Teilproblems in Zukunft mehrmals verwendet werden soll.
Lassen Sie uns dies anhand eines Beispiels verstehen. Angenommen, wir versuchen, die Fibonacci-Serie zu finden. Dann,
Divide and Conquer-Ansatz:
fib (n) Wenn n <2, gib 1 zurück, sonst gib f (n - 1) + f (n - 2) zurück
Dynamischer Ansatz:
mem = () fib (n) Wenn n in mem: return mem (n) else, Wenn n <2, f = 1 else, f = f (n - 1) + f (n - 2) mem (n) = f return f
In einem dynamischen Ansatz speichert mem das Ergebnis jedes Teilproblems.
Vorteile des Divide and Conquer-Algorithmus
- Die Komplexität für die Multiplikation zweier Matrizen mit der naiven Methode beträgt O (n 3 ), während die Verwendung des Divide and Conquer-Ansatzes (dh der Strassen-Matrixmultiplikation) O (n 2,8074 ) beträgt . Dieser Ansatz vereinfacht auch andere Probleme, wie den Turm von Hanoi.
- Dieser Ansatz eignet sich für Multiprozessorsysteme.
- Es nutzt Speicher-Caches effizient.
Anwendungen teilen und erobern
- Binäre Suche
- Zusammenführen, sortieren
- Schnelle Sorte
- Strassens Matrixmultiplikation
- Karatsuba-Algorithmus
