Diskussion:Binäre Suche

Automatische Archivierung

Auf dieser Seite werden Abschnitte ab Überschriftenebene 2 automatisch archiviert, die seit 14 Tagen mit dem Baustein {{Erledigt|1=--~~~~}} versehen sind. Die Archivübersicht befindet sich unter Archiv.

Binäre Suche#Erwartungswert der Komplexität

Überschrift und Zweck des genannten Abschnitts sind mir etwas rätselhaft:

1. IMHO gibt es einen Erwartungswert von asymptotischen Größen (»Komplexität«, O-Notation) nicht. Allenfalls einen Erwartungswert (≈ Mittelwert) für die Anzahl der Suchschritte.
2. Wenn als Ergebnis nur ${\mathcal {O}}(\log \ n)$ herausgearbeitet werden soll, dann ist das anderswo einfacher und direkter erledigt und der Formelkram unnötig.
3. Dass die Suchmenge immer 2ⁿ Elemente enthält, ist bei einem derartigen Rechenaufwand eine unzulässige Vereinfachung.
4. Es fehlt eine Angabe, woher die ganze Überlegung und Rechnung stammt.

--Nomen4Omen (Diskussion) 17:03, 2. Nov. 2015 (CET)

lieber Nomen4Omen, ich muss dir teilweise widersprechen:

1. Ich gebe dir recht, da müsste die Überschrift heißen 'Erwartungswert der Anzahl der Abfragen'
2. Die durchschnittlichen Kosten können durchaus kleiner sein als die Komplexität als maximale Kosten. In diesem Falle ist es nicht der Fall, musste aber gezeigt werden.
3. Du hast offenbar den Beitrag nicht richtig gelesen, denn dort wurde angenommen dass die Suchmenge kleiner oder gleich als eine Potenz von 2 ist.
4. Die Überlegung stammt von jemand der sich auch mal für den Durchschnitt der Suchkosten interessiert, in diesem Falle von mir. Die dort verwendete Rechnung dürfte wohl nachvollziehbar sein.

--Ym0510 (Diskussion) 3. Jan. 2016 (CET) (14:38, 3. Jan. 2016 (CET), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

@Ym0510

1. Wie ich mit dem Hinweis auf Erwartungswert (den Du ja eigentlich selbst schon drin hast) ausdrücken wollte, hat dieser mit Verteilungen zu tun. Und ohne eine Annahme über diese ist Deine Aussage falsch, da es Verteilungen gibt, bei denen eine von der Mächtigkeit der Suchmenge unabhängige Komplexität herauskommt. Beispiel: Zugriffswahrscheinlichkeit auf Element_i = 2^-i. Dann dominiert nämlich das erste Element die ganze Komplexität, so dass ≈ ½ herauskommt. (Allerdings sind bei diesem Beispiel die maximalen Kosten dann proportional.)
2. Erster Satz ist richtig. Zweiter Satz ist falsch: siehe 1.
3. Dass die Suchmenge kleiner oder gleich als eine Potenz von 2 ist, ist (zwar sprachlich falsch, aber) arithmetisch immer richtig. Im betroffenen Abschnitt habe ich einen Nachweis für $C(N)\leq C(2^{n})$ nicht gesehen. (Zugegeben: Ich hab's gar nicht richtig gelesen, weil ich schon Deine Annahme $P(\omega _{1})={\frac {1}{2^{n}}}$ nicht verstanden habe bzw. mir falsch vorkam. Siehe auch 1., wo bei mir $P(\omega _{1})={\frac {1}{2}}$ herauskommt.)
4. Wikipedia:Belege und WP:OR erwarten zuverlässige Belege.

--Nomen4Omen (Diskussion) 15:38, 3. Jan. 2016 (CET)

@Nomen4Omen

1. Wenn du den Beitrag gelesen hättest, hättest Du gesehen dass in der dort definierten Rekursion die Annahme der Gleichverteilung bereits enthalten ist.
2. Sowohl erster als auch zweiter Satz ist richtig, siehe 1.
3. Wenn du den Beitrag gelesen hättest dann hättest gesehen dass dort die Formulierung 'für $N\leq 2^{n}$ ' steht, also $N$ und $n$ sind so dass die Ungleichheit gilt. Ebenso hättest du gesehen dass genau $C(N)\leq C(2^{n})$ gezeigt wurde. Es sieht so aus dass du hier Wahrscheinlichkeit und Komplexität durcheinander bringst: in deinem Punkt 1. oben schreibst du die Zugriffswahrscheinlichkeit aus $2^{i}$ Elementen ist $2^{-i}$ und die Komplexität 1/2. Hier behauptest du die Zugriffswahrscheinlichkeit aus $2^{n}$ Elementen wäre 1/2. Ich empfehle dir den Beitrag zu lesen, bevor du mit mir darüber diskutierst, denn ich habe langsam keine Lust den ganzen Beitrag hier wiederzugeben.

1. Mit Hinweis auf Reihe Mathematik sind die nötigen Referenzen erbracht. Mitdenken muss man etwas auch wenn man so etwas verstehen will.

Ym0510 (Diskussion) 12:16, 5. Jan. 2016 (CET)

@Ym0510
Ich habe Deinen alten Beitrag vorliegen, und Du musst ihn nicht wiederholen.
Zu 1a: In Deinem 2. Satz im besagten Beitrag steht: „Die Wahrscheinlichkeit das Suchargument aus ... zu finden ist dann ...“. Das lese ich als eine Schlussfolgerung und nicht so, dass Du damit die Gleichverteilung voraussetzst. Und ich sehe nicht, wo Du diese sonst vorausgesetzt haben willst. Wenn Du vom Leser verlangst, dass er in Deiner „dort definierten Rekursion die Annahme der Gleichverteilung bereits“ erkennt, verlangst Du zu viel von ihm. Ich habe Dich niemals so gelesen. Ein Begriff «Gleichverteilung», «Gleichverteiltheit» oder «gleichverteilt» kommt in Deinem Text nicht vor, denn beim Suchen mit der Browser-Suchfunktion auf «leichv» sagt der: «Keine Übereinstimmung.»
(Aber auch jetzt, wo ich erkenne, dass Du es gleichverteilt gemeint hast, mag ich nicht akzeptieren, dass für den Beweis von »gleichverteilter Durchschnitt verhält sich asymptotisch nicht besser als gleichverteilter worst case« solcher Formelkram erforderlich sein soll.)
Zu 3: Mein Beispiel einer extremen Ungleichverteilung in meinem Punkt 1. vom 3. Jan. 2016 mit einem beschränkten Mittelwert (d.h. wesentlich besser als der worst case) für die Suchschritte (unabhängig von der Anzahl der Elemente) ist nicht vollständig. Angesichts des riesigen Missverständnisses über die Gleichverteilung ist wohl überflüssig, es in Ordnung zu bringen. --Nomen4Omen (Diskussion) 15:19, 5. Jan. 2016 (CET)

@Nomen4Omen
Ich verstehe nicht dass ein Missverständnis das durch den Zusatz "...bei Annahme von Gleichverteilung...' behoben werden kann ein riesiges sein soll. Zumal wenn man die Rekursion sieht sofort erkennt dass dies eine Gleichverteilungsannahme ist. Du bist natürlich nicht darauf gekommen weil Du es nicht gelesen hast.

"(Aber auch jetzt, wo ich erkenne, dass Du es gleichverteilt gemeint hast, mag ich nicht akzeptieren, dass für den Beweis von »gleichverteilter Durchschnitt verhält sich asymptotisch nicht besser als gleichverteilter worst case« solcher Formelkram erforderlich sein soll.)".

Erstens ist diese Formulierung nicht korrekt da der Begriff worst case von seiner Definition her keiner w-Verteilung unterliegt - sonst wäre er ja kein worst case - so dass sie korrekterweise heißen müsste 'der erwartungswert unter Gleichverteilungsannahme ist gleich aufwendig wie der worst case Fall'. Somit zweitens die Frage an Dich: wie würdest Du diese Aussage ohne den 'Formelkram' zeigen?

--Ym0510 (Diskussion) 16:47, 9. Jan. 2016 (CET)

@Ym0510
Es ist schon ein starkes Stück: Am 13.01.2013 hast Du Deinen Beitrag Binäre Suche#Erwartungswert der Komplexität veröffentlicht. Kein Wort von Gleichverteilung, nur Formelkram und der ach so hilfreiche Hinweis „(s. auch Reihe (Mathematik))“, der dazuhin als Beleg für den Formelkram herhalten soll. Ziemlich genau 3 Jahre später und nachdem Du in der Enge bist, blaffst Du zurück, dass es sich um eine Gleichverteilung handelt und dass man die hätte erahnen können, wenn man Deinen Formelkram gelesen hätte. Nach all diesem beharrst Du darauf, dass dies keine grobe Irreführung war, sondern dass das Missverständnis durch den Zusatz "...bei Annahme von Gleichverteilung...' hätte behoben werden können. Ein starkes Stück fürwahr. (Am Ende würde es mich nicht wundern, wenn Du triumphierend verkünden würdest, dass das alles eine riesige Verarsche war.)
Dabei ist das Ganze sehr einfach: Die binäre Suche im Array läuft – wie unter #Algorithmus beschrieben – völlig determiniert ab. Der einzige Freiheitsgrad ist der, ob man bei der Mittelwertbildung der Indices, wenn die Summe nicht durch 2 teilbar ist, nach unten oder nach oben rundet (was aber am Laufzeitverhalten nichts ändert). Wenn man dieses Verfahren in einem binären Entscheidungsbaum abbildet, erhält man einen sog. vollständigen Binärbaum. Das ist einer, bei dem jede Ebene bis auf die unterste voll ist. Im Artikel Binärer Suchbaum#Suchtiefen und Pfadlängensummen wird die Anzahl der Vergleiche ${\underline {S}}_{\mathfrak {e}}(n)$ für alle Pfade von der Wurzel bis zu jedem Knoten im Baum – das ist die dortige Zugriffsverteilung ${\mathfrak {e}}$, bei der alle Knoten gleich wahrscheinlich sind – gegeben durch ${\underline {S}}_{\mathfrak {e}}(n)=1+(n+1)k-2^{k}$ mit $\scriptstyle 2^{k-1}\leq n+1\leq 2^{k}$. Für den Mittelwert muss man ${\underline {S}}_{\mathfrak {e}}(n)$ nur noch durch $n$ dividieren. --Nomen4Omen (Diskussion) 21:57, 10. Jan. 2016 (CET)

Kriegt Euch mal wieder ein. Ohne (starke) Annahmen gibt es kein Ergebnis. Die mittlere Pfadlänge im Binärbaum betrifft nur die erfolgreiche Suche, und nimmt (Mittelwert!) an dass alle Elemente gleich oft gesucht werden. Ändern wir die Annahme wie die Suchen verteilt sind ab, und suchen wir immer den Median (bei ungerader Anzahl), so bekommen wir O(1) als Suchzeit! Das reale Suchverhalten wird also irgendwo dazwischen liegen. Deswegen: Keine Beweise auf Wikipedia führen (Theoriefindung), sondern Primärquellen verlinken. (nicht signierter Beitrag von 91.52.13.120 (Diskussion) 11:45, 11. Jan. 2016 (CET))

@91.52.13.120 mit dem letzten Hinweis darüber wie die Natur eines Beitrags in Wikipedia sein sollte kann ich jedenfalls mehr anfangen als mit dem letzten Einwurf (des bisherigen Diskutanten) dessen erster Teil außer Polemik nichts zur Sache beiträgt und kein Bisschen Beachtung verdient und dem zweiten Teil der meint dass der naive Kram dort mehr wert sein soll als der Formelkram.

--Ym0510 (Diskussion) 16:47, 9. Jan. 2016 (CET)

@Ym0510
Wirklich mein letztes Wort in dieser Sache: Oben, in Deinem Beitrag vom 14:38, 3. Jan. 2016 schreibst Du: „Die durchschnittlichen Kosten können durchaus kleiner sein als die Komplexität als maximale Kosten. In diesem Falle ist es nicht der Fall, musste aber gezeigt werden.“ In Deinem Beitrag vom 13.01.2013 schreibst Du aber nur etwas von „Erwartungswert von $C(N)\leq ...=2n+{\frac {1}{2^{n}}}$ und somit wieder von der Komplexitätsklasse ${\mathcal {O}}(\log \ n)$.“
Im Verstehen, wie Du mit einer solchen Ungleichung gezeigt haben willst, dass die durchschnittlichen Kosten nicht kleiner sind als die maximalen Kosten, da scheitere ich abgrundtief. --Nomen4Omen (Diskussion) 20:57, 20. Jan. 2016 (CET)
Nachtrag: Ach ja, nicht einmal bei der Wahl der Variablennamen scheinst Du aufzupassen: Kommt im Zitat hier $n$ doch in zwei völlig verschiedenen Bedeutungen vor! --Nomen4Omen (Diskussion) 11:03, 21. Jan. 2016 (CET)