Binärer Suchalgorithymus - wie ensteht das log2(n)-1
-
Das VErständnis das man bei der Binären suche immer in die Mitte und dann in die Mitte der rechten und linken spalte springt(grob gesagt) habe ich schon verstanden doch wie ensteht das
"log2(n)-1"im im Normal Fall betrachtet (In Beziehung zu welchen angaben)
ksnn mir das einer einfach erklären :p
-
Warum da ein -1 steht, weiss ich auch nicht (lässt man in der Big-O-Notation onehin weg). Binäre Suche hat eine Laufzeit von O(log n). Warum:
Angenommen du hast n Einträge und machst i Schritte. Pro Schritt halbierst du den Bereich, in dem du Suchen musst. Du kannst in i Schriiten 2^i Einträge durchsuchen.
Du erhälst also die Gleichung: 2^i=n <==> i = log(n), d.h. also du brauchst log(n) Schritte.
-
Mit der genauen Angabe, welcher Logarithmus gemeint ist, vermute ich mal, dass hier nicht die Laufzeitkomplexität in O-Notation gemeint ist, sondern eine exakte Angabe. icarus2 hat schon erklärt, warum man höchstens log2(n)-Schritte (aufgerundet!) benötigt. Das -1 wird daher kommen, dass man nur in der Hälfte der Fälle bis zum letzten Schritt gehen muss und ansonsten den Suchwert schon auf dem Weg findet. Warum sich das aber exakt zu -1 ergeben soll, weiß ich jetzt auch nicht. Ich hätte einen Wert ein klein wenig kleiner als -1 (also eher Richtung -1.1) geschätzt, weil die Angabe -1 das Ergebnis wäre, wenn man im vorletzten Schritt fündig wird, was nur die Hälfte der Fälle sind in denen man vor dem letzten Schritt fündig wird. Aber solche intuitiven Schätzungen sind oft falsch. Da Sonntag ist und das Mittagessen schwer im Magen liegt, mag ich aber gerade nicht selber rechnen :p .
Aber Wikipedia rettet uns mal wieder!
Da steht, log2(n)-1 wäre nur eine ungefähre Angabe. Habe also richtig geschätzt
.
-
Wofür ist es denn wichtig zu wissen, ob es log(n)-1 oder log(n)-1.2 (oder wie viel auch immer) ist? Weil es ist ja nicht wirklich exakter.
-
icarus2 schrieb:
Wofür ist es denn wichtig zu wissen, ob es log(n)-1 oder log(n)-1.2 (oder wie viel auch immer) ist? Weil es ist ja nicht wirklich exakter.
Wieso? Das eine wäre exakt, das andere nicht.
-
SeppJ schrieb:
Wieso? Das eine wäre exakt, das andere nicht.
Naja, "exakt" im Sinne von: Der Erwartungswert unter bestimmten statistischen Annahmen die Eigenschaften des Inputs betreffend...
-
dot schrieb:
SeppJ schrieb:
Wieso? Das eine wäre exakt, das andere nicht.
Naja, "exakt" im Sinne von: Der Erwartungswert unter bestimmten statistischen Annahmen die Eigenschaften des Inputs betreffend...
Aber trotzdem exakt. Und die Annahme ist die Annahme, dass man nichts weiß und alles Zufall ist. Also der Regelfall. Und da der Logarithmus so langsam steigt ist bei einer exakten Analyse schon wichtig, ob der Durchschnittswert log2(n) ist oder doch eher log2(n)-1. Wie exakt das -1 nun ist, ist aber dann doch nicht ganz so wichtig, insofern haste Recht. Die Zahl sollte sich aus einer geometrischen Reihe ergeben und der Grenzwert für n->unendlich dürfte nicht zu weit von -1 entfernt sein.
