Komplexität der Sprungsuche



  • Mit Einersprüngen meine ich die anschließennde lineare Suche im letzten Intervall.

    freakC++ schrieb:

    Da gibt es diesen Einersprung nicht mehr. Gilt die Sprungweite sqrt(n) also nur für die Lineare Suche, wie auch aus deimem letzten Post vermute?

    Ja.
    Aber wer kam eingentlich auf die schräge Idee, binäre Suche für des letzte Intervall benutzen zu dürfen?



  • Ich! Wenn das Intervall groß genug ist 🙂

    Ich wollte die Sprungsuche mal implementieren. Dabei gehe ich so vor:

    while(jmp > n) {//...}
    

    jmp ist das aktuelle Element nach dem Sprung (es wird immer "step" aufaddiert und n ist die Arraygröße). Alles funktioniert auch soweit, außer wenn das gesuchte Element im letzten Intervall liegt. Dieses wird dann nämlich meist übersprungen, da "jmp" größer als "n" wird, weshalb die Schleife abbricht. Hast Du eine Idee, wie ich dieses Problem auf schöne Art lösen könnte?

    Vielen Dank
    lg, freakC++



  • 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 😉


Anmelden zum Antworten