Ist die Suche im Goldenen Schnitt besser als die Binärsuche?

Kürzlich habe ich eine Meinung gehört, dass die binäre Suche verbessert werden könnte, indem man den Bereich durch Phi (Golden Ration) anstatt durch 2 aufspaltet. Das war eine große Überraschung für mich, weil ich noch nie von einer solchen Optimierung gehört habe. Ist das wahr? Wäre das der Fall gewesen, wenn die Division durch 2 und durch Phi gleichermaßen performant gewesen wäre?Ist die Suche im Goldenen Schnitt besser als die Binärsuche?

Falls nicht, gibt es irgendwelche allgemeinen Bedingungen, unter denen die Suche nach Goldabschnitten schneller als die binäre Suche durchgeführt werden würde?

UPD: Bearbeitet, um den Link zu einem nicht relevanten Wikipedia-Artikel zu entfernen. Entschuldigung für die Irreführung.

Quelle

2010-11-22 Fixpoint

Es gibt zwei Algorithmen namens "Fibonacci Suche".

The article you linked ist ein numerischer Algorithmus zum Finden des Maximums oder Minimums bestimmter Funktionen. Es ist der optimale Algorithmus für dieses Problem. Dieses Problem unterscheidet sich nur von dem binären Suchproblem, das für jeden gegebenen Fall offensichtlich sein sollte.

The other kind of Fibonacci search greift das gleiche Problem wie binäre Suche an. Binäre Suche ist grundsätzlich immer besser. Knuth schreibt, dass die Fibonacci-Suche "auf einigen Computern vorzuziehen ist, da es nur Addition und Subtraktion, nicht Division durch 2, beinhaltet." Aber fast alle Computer verwenden binäre Arithmetik, bei der die Division durch 2 einfacher als Addition und Subtraktion ist.

(Der derzeit Wikipedia-Artikel behauptet, dass Fibonacci-Suche besser Referenzlokalität haben könnte, hat ein Anspruch Knuth nicht machen. Es konnten, vielleicht, aber das ist irreführend. Die durch eine Fibonacci-Suche durchgeführt Tests sind näher zusammen, gerade insofern, als sie weniger hilfreich sind, den Bereich einzugrenzen, was im Durchschnitt mehr Lesevorgänge von mehr Teilen der Tabelle zur Folge hätte, nicht weniger. Wenn die Aufzeichnungen tatsächlich auf Band gespeichert werden, so dass die Suchzeiten dominieren, dann Fibonacci Suche könnte schlagen binäre Suche —, aber in diesem Fall beide Algorithmen sind weit von optimal.)

Quelle

2010-11-22 16:24:00

Anstelle der Handbewegung wäre es besser, uns die komplexen Fibonacci-Suchen mitzuteilen, die im Wikipedia [artikel] (http: //en.wikipedia.org/wiki/Fibonacci_search) (es gibt nur eine gegebene Komplexität und das ist, ohne zu sagen, welcher Typ es ist - nutzlose * Information *). –

Die Unterschiede sind Konstante-Faktor. Im Direktzugriffsspeicher sind Binärsuche und Fibonacci-Suche beide O (log n). Wenn Sie ein Band durchsuchen, sind beide O (n). –

"arbeitet schneller" ist vage; aber die binäre Suche sollte den niedrigsten Worst-Case für die Anzahl der Zugriffe haben.

Quelle

2010-11-22 15:49:57 lijie

wie in, jede Methode, die die geteilte Region verzerrt wird mehr haben greift zu, wenn das gesuchte Objekt in der größeren Region endet. Der durchschnittliche Fall kann sinken, aber der schlimmste Fall wird zunehmen. Ähnliche Konzepte in der Codierung (im Sinne von Shannon). – lijie

... um diese letzte Note zu erweitern - und die verzerrte Methode wird im Durchschnitt besser sein, wenn das gesuchte Element häufiger in der kleineren Region gefunden wird. Das wird nur passieren, wenn Sie eine gute Möglichkeit haben zu entscheiden, welche Seite kleiner sein sollte, basierend auf etwas Wissen über die Art der Daten. – greggo

Ich vermisse etwas hier, aber nach dem Blick auf den Wikipedia-Eintrag in der Golden Section Suche scheint es, dass es nicht das gleiche Problem löst wie eine binäre Suche überhaupt. Während eine binäre Suche nützlich ist, um einen Wert in einer sortierten Liste zu finden, wird eine Suche nach einem goldenen Schnitt verwendet, um einen minimalen oder maximalen Wert einer Funktion über einen Bereich von Werten zu finden.

Quelle

2010-11-22 15:54:03 Ferruccio

Richtig, sie sind für verschiedene Zwecke und optimal unter verschiedenen Bedingungen. Halbierung dient zum Finden von "Wurzeln" oder Orten, an denen sich eine Eigenschaft ändert, und ist optimal zum Verfeinern von "Abstandspaaren" - Paaren von Orten, für die das Zeichen (Eigenschaft) unterschiedlich ist. Die Suche im Goldenen Schnitt dient zur Minimierung/Maximierung und ist optimal für die Verfeinerung von "Belichtungsreihen", Tripeln von Punkten a, b, c, so dass a mokus

Ist die Suche im Goldenen Schnitt besser als die Binärsuche?

Antwort

Verwandte Themen