Big O Binary Search - bin verwirrt

[phl92]

Bin unsicher ob so eine spezifische Frage erlaubt ist, aber versuchen kann ichs mal. Da hier sicher viele Informatiker sind, ist diese Berechnungen sicher nicht neu:

Ich lern im Datenstruktur & Algorithmen Kurs gerade die Laufzeitberechnungen der Such-/Sortier Algorithmen. Grundsärtzlich ist mir das meistens klar, aber ich bin grad den Binary Search (der, bei dem immer alles durch 2 geteilt wird, bis das Ziel gefunden wird) selbst durchgegangen und habe ein kontroverses Ergebnis einmal bekommen.

Angenommen wir haben folgendes Array:
num[8]={ 1, 2, 3, 4, 5, 6, 7, 8 ]

also genau 8 Nummern, aber wie in IT üblich startet die erste Zahl im Array bei Index 0.
Dementsprechend habe ich am Anfang, um die Mitte zu berechnen, die 7 als höchste Zahl
low = 0, high = 7 --> mid = (low + high) / 2 --> 3,5 (abgerundet : 3)

um jetzt zB die Zahl 1 zu finden (also die erste im Array), braucht es nur noch mal 2mal eine Splittung durch 2.
Was ja auch formell bestätigt wird, da der log von 8 = 3 ist. Also 3 Schritte.

Wenn ich aber jetzt nicht die Zahl 1 suchen würde, sondern die letzte Zahl, im Bsp oben, die Zahl 8, dann brauch ich sogar 4 Schritte insgesamt. Aber das kann doch eigentlich nicht sein? Bins mehrmals am Zettel mit Stift&Papier durchgegangen und es ist genau 1 Schritt mehr, wenn man eben die letzte Zahl (ganz rechts) vom Array will und nicht die erste Zahl ganz links. (Was ja auch klar ist, da beim Teilen immer abgerundet wird 7 / 2 = 3; usw ...

 

[nik_]

Bitte deine Vorgehensweise hier mal aufschreiben. Laut dieser Seite hier wird die Mitte bestimmt und dann mit dem größeren oder in deinem Fall kleineren Element weiter gemacht.
https://medium.com/@samip.sharma963/binary-search-and-its-big-o-3333d13bd6ec

Bei dir also wäre das dann 7/2 = 3,5. Abgerundet 3. Dann prüfst du, ist die 3 die gesuchte Zahl, wenn nein, mache weiter.
Dein nächstes Array hat aber nur noch die Werte [1,2]. Dann prüfst du, ist die 2 dein Wert, weil der Split Emmas Array [1] übrig lässt. Dann prüfst du die 1 im letzten Schritt und fertig.

Selbes für z.b. die 8.
1. Durchgang. Prüfe ob 3=8 => falsch
Mitte bestimmen in dem du den Startwert auf den alten Mittewert + 1 setzt: Neues Array [4,5,6,7,8].
Mitte bestimmen. Wäre jetzt: 6; 6!=8
Mitte bestimmen und das neue Array ist dann [7,8]. 7!=8
Wieder neue Mitte bestimmen, in dem Fall Mitte = Ende und dann hast du 8=8.

Sind insgesamt 4 Schritte.
Vielleicht ist es hier noch einmal besser erklärt:
https://towardsdatascience.com/introduction-to-big-o-notation-820d2e25d3fd

 

[phl92]

Ganz genau, so rechne ich das auch. Nur ist meine Frage, ob es nicht max 3 Schritte sein sollten?

Du hast ja für den Wert "1" drei Schritte benötigt und für den Wert "8" vier Schritte. Also einen Schritt mehr.

Ich dachte nur und vielleicht lieg ich damit falsch, dass mathematisch gesehen, es max. 3 Schritte (egal für welchen Wert auch immer) geben darf, da der log (2er log) von 8 nun eben mal 3 ist. 2 hoch 3 = 8. Aber vielleicht lieg ich damit falsch und formell bedeutet das nichts.
Weißt du was ich meine? Es muss ja eine mathematische Berechnung geben, um zu klären was das worst Case Szenario ist, und das macht man ja mit diesen Big O Notationen?!

 

[BeBur]

Weißt du was ich meine? Es muss ja eine mathematische Berechnung geben, um zu klären was das worst Case Szenario ist, und das macht man ja mit diesen Big O Notationen?!

Nein, BigO gibt nicht den worst case an. Das ist eine obere Schranke bezüglich des Anstiegs. f ∈ O(log(n)) bedeutet lediglich, dass f für immer weiter steigendes n nicht stärker ansteigt als log(n), d.h. lim f/log(n) < infty.
D.h. insbesondere auch, dass es dabei um das asymptotische Verhalten für gegen unendlich handelt. Es kommt durchaus vor, dass z.B. zwar f ∈ O(log(n)) gilt, aber f sich erst für größere n, z.B. n=100.000 dem Logarithmus annähert und bis dahin deutlich schlechter ist. Ich habe gerade kein Beispiel im Kopf, aber sicherlich werdet ihr Beispiele dafür noch sehen.

Eine andere Definition siehe Link macht das noch deutlicher:
f(n) = O(g(n)) per Definition genau dann wenn wenn N > 0 und C > 0 existieren, so dass |f(n)| ≤ Cg(n)| gilt für alle n>N. Wichtig ist hierbei, dass C eine Konstante ist. Durch N und C hast du also quasi zwei Ungenauigkeiten bei der Notation. Zum Einen kann N sehr groß sein (100.000 im Beispiel im vorherigen Abschnitt), zum Anderen kann auch das C sehr groß sein, d.h. f ist womöglich immer tausendfach langsamer als g(n).

Der "worst case" ist eine eigene Kategorie, unabhängig von der O Notation.

 

[nik_]

Das mit dem Woratcase ist im 2. Link von mir beschrieben

 

[KitKat::new()]

Es muss ja eine mathematische Berechnung geben, um zu klären was das worst Case Szenario ist, und das macht man ja mit diesen Big O Notationen?!

O(logn) heißt, dass es eine Konstante c gibt, sodass c*logn eine obere Schranke für die wahre Laufzeit ist.

 

[BeBur]

O(logn) heißt, dass es eine Konstante c gibt, sodass c*logn eine obere Schranke für die wahre Laufzeit ist.

Für hinreichend große n. Für kleine n muss c*logn nicht unbedingt eine obere Schranke sein.

 

[KitKat::new()]

Ist egal, weil du c einfach groß genug wählen kannst

 

[phl92]

Ah danke Leute! Ich dacht schon, dass meine Theorie hier nicht ganz felsenfest war und ich was verwechselt habe.
Jetzt ist mir einiges klarer.

 

[kuddlmuddl]

Außerdem bin ich nicht sicher, ob du schon gesagt hast, dass man bei Binärsuche natürlich nicht nur 1x splittet.
Stell dir vor es sind die Werte 0-999 mit identischem Index. Dann sucht man ja auch nicht '1000' in der zweiten Hälfte mit 500 Schritten.

 

[phl92]

Da kann ich jetzt nicht ganz folgen. Ein Array mit identischen Index aber gleichen Werten? Wie kann man darin überhaupt etwas "suchen"? Steh auf der Leitung

 

[kuddlmuddl]

Das Array bzw die Daten sind egal für mein Beispiel. Wollte nur sagen: Man zerteilt nicht nur 1x sondern log N mal häufig.

 

[abcddcba]

Wollte nur sagen: Man zerteilt nicht nur 1x sondern log N mal häufig.

darum ging es doch in dem ganzen Thread, oder nicht? der TE schreibt sogar im Eingangspost dass mehrmals gesplittet wird

um jetzt zB die Zahl 1 zu finden (also die erste im Array), braucht es nur noch mal 2mal eine Splittung durch 2.
Was ja auch formell bestätigt wird, da der log von 8 = 3 ist. Also 3 Schritte.