Komplexität der Sprungsuche
-
freakC++ schrieb:
Hast Du eine Idee, wie ich dieses Problem auf schöne Art lösen könnte?
Ja. Grobsuche, lineare Suche, binäre Suche und kombinierte Sprungsuche nehmen eine Range und geben eine Range zurück.
-
-
Mmhh...das verstehe ich irgendwie nicht....wie meinst Du das? Wie kriege ich es hin, dass das Element auch gefunden wird, wenn es im letzten Intervall liegt?
-
Den Fall erkennen dürfte auf jeden Fall einfach sein (pos+step>n) - danach mußt du nur die aktuelle Position und das Daten-Ende als Grenzen für die Detailsuche verwenden.
-
CStoll schrieb:
Den Fall erkennen dürfte auf jeden Fall einfach sein (pos+step>n) - danach mußt du nur die aktuelle Position und das Daten-Ende als Grenzen für die Detailsuche verwenden.
Daran hatte ich auch gedacht. Das bedeutet, dass ich aber immer das letzte Interval untersuchen müsste. Ich könnte mir auch das letzte Element anschauen und prüfen, ob es größer als das gesuchte ist. Erst wenn dies der Fall ist, untersuche ich das letzte Intervall.
Ich dachte, es gäbe irgendwie noch eine elegante Lösung ;). Man könnte auch die Sprungweite so bestimmen, dass es genau aufgeht. Dann ist sie aber fast nie sqrt(n) und damit nicht am effizientesten (bei einer linearen Suche)
lg, freakC++
-
freakC++ schrieb:
Man könnte auch die Sprungweite so bestimmen, dass es genau aufgeht.
Dagegen gibt es zum Glück Primzahlen.
-
geht also nicht immer
-
Ist eigentlich die Komplexität n log(n) dasselbe wie log2(n). Mathematisch jedenfalls nicht. Manchmal hat die Binärsuche die und dann wieder die andere Komplexität. Was nu?
Danke
-
lg(n) und n lg(n) sind zwei grundsätzlich verschiedene Komplexitätsklassen. lg(n) läuft in sublinearer Zeit, n lg(n) (für hinreichend große n) nicht.
Eine Binärsuche, die in n lg(n) läuft, wäre ziemlich nutzlos. Wenn das irgendwo steht, dann ist es normalerweise ein Fehler.
-
freakC++ schrieb:
CStoll schrieb:
Den Fall erkennen dürfte auf jeden Fall einfach sein (pos+step>n) - danach mußt du nur die aktuelle Position und das Daten-Ende als Grenzen für die Detailsuche verwenden.
Daran hatte ich auch gedacht. Das bedeutet, dass ich aber immer das letzte Interval untersuchen müsste. Ich könnte mir auch das letzte Element anschauen und prüfen, ob es größer als das gesuchte ist. Erst wenn dies der Fall ist, untersuche ich das letzte Intervall.
Am Ende der Suche hast du die Position so bestimmt, daß dein Wert zwischen pos und pos+step liegt (wobei letzteres möglicherweise außerhalb der Array-GRenzen liegt). Damit kannst du für die Detailsuche das Intervall von pos bis min(pos+step,n) verwenden.
freakC++ schrieb:
Ist eigentlich die Komplexität n log(n) dasselbe wie log2(n). Mathematisch jedenfalls nicht. Manchmal hat die Binärsuche die und dann wieder die andere Komplexität. Was nu?
Danke
Woher hast du denn das mit dem O(n log n)? Das gilt vielleicht für Sortieralgorithmen, aber eine n log n Suche wäre wphl reichlich langsam
