Divide-and-Conquer-Algorithmus ist eine Problemlösungsstrategie, bei der ein komplexes Problem in kleinere, besser beherrschbare Teile zerlegt, jeder Teil einzeln gelöst und dann die Lösungen kombiniert werden, um das ursprüngliche Problem zu lösen. Es handelt sich um eine weit verbreitete algorithmische Technik in der Informatik und Mathematik.

Beispiel: Im Zusammenführen, sortieren Algorithmus, der Teile und herrsche Die Strategie wird zum Sortieren einer Liste von Elementen verwendet. Das folgende Bild veranschaulicht die Teilungs- und Zusammenführungszustände zum Sortieren des Arrays Zusammenführen, sortieren .

Java-String in Booleschen Wert umwandeln

Inhaltsverzeichnis

• Was ist „Teile und herrsche“?
• Phasen des Teilens und Eroberns
• Anwendungen von Divide and Conquer
• Grundlagen von Divide and Conquer
• Standardalgorithmen zum Teilen und Erobern
• Probleme, die auf der binären Suche basieren
• Üben Sie Aufgaben zum Thema „Teile und herrsche“.

Was ist der Divide-and-Conquer-Algorithmus?

Divide and Conquer ist eine Problemlösungstechnik, bei der ein größeres Problem in Teilprobleme zerlegt, die Teilprobleme unabhängig voneinander gelöst und die Lösungen dieser Teilprobleme kombiniert werden, um die Lösung des größeren Problems zu erhalten.

Stufen des Divide-and-Conquer-Algorithmus:

Der Divide-and-Conquer-Algorithmus kann in drei Phasen unterteilt werden: Teilen , Erobern Und Verschmelzen .

1. Teilen:

• Zerlegen Sie das ursprüngliche Problem in kleinere Teilprobleme.
• Jedes Teilproblem sollte einen Teil des Gesamtproblems darstellen.
• Ziel ist es, das Problem so lange zu teilen, bis keine weitere Teilung mehr möglich ist.

2. Erobere:

• Lösen Sie jedes der kleineren Teilprobleme einzeln.
• Wenn ein Teilproblem klein genug ist (oft als Basisfall bezeichnet), lösen wir es direkt ohne weitere Rekursion.
• Ziel ist es, eigenständig Lösungen für diese Teilprobleme zu finden.

3. Zusammenführen:

• Kombinieren Sie die Teilprobleme, um die endgültige Lösung des Gesamtproblems zu erhalten.
• Sobald die kleineren Teilprobleme gelöst sind, kombinieren wir ihre Lösungen rekursiv, um die Lösung des größeren Problems zu erhalten.
• Ziel ist es, durch Zusammenführung der Ergebnisse der Teilprobleme eine Lösung für das ursprüngliche Problem zu formulieren.

Anwendungen des Divide-and-Conquer-Algorithmus:

• Zusammenführen, sortieren: Die Zusammenführungssortierung ist ein klassisches Beispiel für einen Divide-and-Conquer-Sortieralgorithmus. Es zerlegt das Array in kleinere Unterarrays, sortiert sie einzeln und führt sie dann zusammen, um das sortierte Array zu erhalten.
• Medianwert: Der Median einer Menge von Zahlen kann mithilfe eines Divide-and-Conquer-Ansatzes ermittelt werden. Durch rekursive Aufteilung der Menge in kleinere Teilmengen kann der Median effizient bestimmt werden.
• Min- und Max-Befund: Der Divide-and-Conquer-Algorithmus kann verwendet werden, um gleichzeitig die minimalen und maximalen Elemente in einem Array zu finden. Durch Aufteilen des Arrays in Hälften und Vergleichen der Min-Max-Paare aus jeder Hälfte können die gesamten Min- und Max-Werte in logarithmischer Zeitkomplexität ermittelt werden.
• Matrix-Multiplikation: Der Strassen-Algorithmus zur Matrixmultiplikation ist eine Divide-and-Conquer-Technik, die die Anzahl der für große Matrizen erforderlichen Multiplikationen reduziert, indem die Matrizen in kleinere Untermatrizen zerlegt und ihre Produkte kombiniert werden.
• Problem des engsten Paares: Das Problem des nächsten Paares besteht darin, die beiden nächstgelegenen Punkte in einer Menge von Punkten in einem mehrdimensionalen Raum zu finden. Ein Divide-and-Conquer-Algorithmus, beispielsweise der Divide-and-Conquer-Algorithmus für das engste Paar, kann dieses Problem effizient lösen, indem er die Punkte rekursiv dividiert und die Lösungen aus den Teilproblemen zusammenführt.

Grundlagen des Divide-and-Conquer-Algorithmus:

• Einführung in „Teile und herrsche“.
• Dynamische Programmierung vs. Divide-and-Conquer
• Verringern und erobern
• Erweiterter Hauptsatz für Divide-and-Conquer-Rezidiven

Standardalgorithmen auf Divide-and-Conquer-Algorithmus :

• Binäre Suche
• Zusammenführen, sortieren
• Schnelle Sorte
• Berechnen Sie pow(x, n)
• Karatsuba-Algorithmus für schnelle Multiplikation
• Strassen’s Matrix Multiplication
• Konvexer Rumpf (einfacher Divide-and-Conquer-Algorithmus)
• Quickhull-Algorithmus für konvexen Rumpf

Probleme, die auf der binären Suche basieren:

• Finden Sie ein Spitzenelement in einem bestimmten Array
• Suchen Sie nach einem Mehrheitselement in einem sortierten Array
• K-tes Element zweier sortierter Arrays
• Finden Sie die Anzahl der Nullen
• Suchen Sie die Rotationsanzahl im gedrehten sortierten Array
• Finden Sie den Punkt, an dem eine monoton steigende Funktion zum ersten Mal positiv wird
• Median zweier sortierter Arrays
• Median zweier sortierter Arrays unterschiedlicher Größe
• Das Partitionsproblem des Malers mithilfe der binären Suche

Übe Probleme auf Divide-and-Conquer-Algorithmus :

• Quadratwurzel einer ganzen Zahl
• Maximum und Minimum eines Arrays mit minimaler Anzahl von Vergleichen
• Finden Sie die Häufigkeit jedes Elements in einem Array mit begrenztem Bereich in weniger als O(n) Zeit
• Fliesenproblem
• Inversionen zählen
• Das Skyline-Problem
• Suchen Sie in einem zeilen- und spaltenweise sortierten 2D-Array
• Weisen Sie eine Mindestanzahl an Seiten zu
• Modulare Potenzierung (Potenz in der modularen Arithmetik)

Quicklinks:

• Lernen Sie Datenstruktur und Algorithmen | DSA-Tutorial
• „Übungsaufgaben“ zum Thema „Teile und herrsche“.
• „Quiz“ zum Thema „Teile und herrsche“.