Warum laufen Algorithmen zum Teilen und Überwinden oft schneller als Brute Force? Zum Beispiel, um das nächste Punktepaar zu finden. Ich weiß, du kannst mir den mathematischen Beweis zeigen. Aber intuitiv, warum passiert das? Zauber?Warum laufen Algorithmen zum Teilen und Überwinden oft schneller als Brute Force?
Theoretisch ist es wahr, dass "teile und herrsche immer besser als rohe Gewalt" ist? Wenn nicht, gibt es ein Gegenbeispiel?
Für Ihre erste Frage ist die Intuition hinter Divide-and-Conquer, dass in vielen Problemen die Menge der Arbeit, die getan werden muss, auf einer kombinatorischen Eigenschaft der Eingabe basiert, die mehr als linear skaliert.
Zum Beispiel wird im Problem mit dem nächsten Punktpaar die Laufzeit der Brute-Force-Antwort dadurch bestimmt, dass Sie alle möglichen Punktepaare betrachten müssen.
Wenn Sie etwas nehmen, das quadratisch wächst und es in zwei Teile schneidet, von denen jedes die halbe Größe wie zuvor hat, dauert es ein Viertel der Anfangszeit, um das Problem in jeder Hälfte zu lösen, also das Problem in beiden zu lösen Hälften brauchen etwa die Hälfte der Zeit, die für die Brute-Force-Lösung benötigt wird. Es in vier Stücke zu schneiden würde ein Viertel der Zeit dauern, es in acht Stücke schneiden ein Achtel der Zeit, etc.
Die rekursive Version endet in diesem Fall schneller, weil bei jedem Schritt vermeiden wir viel tun arbeiten Sie mit dem Umgang mit Elementpaaren, indem Sie sicherstellen, dass nicht zu viele Paare vorhanden sind, die wir tatsächlich überprüfen müssen. Die meisten Algorithmen, die eine Lösung zum Teilen und Überwinden haben, werden aus ähnlichen Gründen schneller.
Für Ihre zweite Frage, Nein, Divide and Conquer-Algorithmen sind nicht unbedingt schneller als Brute-Force-Algorithmen. Berücksichtigen Sie das Problem, den Maximalwert in einem Array zu finden. Der Brute-Force-Algorithmus benötigt O (n) -Zeit und verwendet O (1) -Raum, wie es einen linearen Scan über die Daten macht. Der Divide-and-Conquer-Algorithmus wird hier angegeben:
Das kostet Zeit O (n) als auch, verwendet aber O (log n) Speicher für den Stapelspeicher. Es ist eigentlich schlimmer als der einfache lineare Algorithmus.
Als ein anderes Beispiel hat die maximum single-sell profit problem eine Lösung zum Teilen und Überwinden, aber die optimierte dynamische Programmierlösung ist schneller in Bezug auf Zeit und Speicher.
Hoffe, das hilft!
Ich empfehle Ihnen, lesen Sie das Kapitel 5 von Algorithmus Design, es erklärt sehr gut teilen und herrschen.Für ein Problem, wenn Sie es in zwei Teilprobleme mit dem gleichen Muster wie dem Ursprung teilen können, und die Zeitkomplexität, um die Ergebnisse der zwei Teilprobleme in das Endergebnis zusammenzuführen, ist irgendwie klein , dann ist es schneller, als das ursprüngliche vollständige Problem durch Brute-Force zu lösen.
Wie gesagt in Algorithm Design, man kann tatsächlich nicht zu viel gewinnen von Teilen-und-herrschte in Bezug auf Zeit, allgemein kann man nur Zeit Komplexität von höheren Polynom reduziert Polynom zu senken (zB von O (n^3) zu O (n^2)), aber kaum von Exponential zu Polynom (zB von O (2^n) zu O (n^3)).
Ich glaube, das Beste, was du von divide-and-conquer gewinnen kannst, ist die Denkweise für die Problemlösung. Es ist immer ein guter Versuch, das ursprüngliche große Problem auf kleinere und leichtere Teilprobleme zu reduzieren. Selbst wenn Sie keine bessere Laufzeit bekommen, hilft es Ihnen trotzdem, das Problem zu durchdenken.
Um einen Kuchen in 16 Stücke zu teilen, ist die erste Lösung zu versuchen, 1/16 des Kuchens und so weiter zu schneiden ... schwierig. Eine andere Lösung besteht darin, den Kuchen in 2, dann wieder in 2, dann jeweils 1/4 in 2 und 1/8 in 2 zu schneiden. –