Komplexität der Sprungsuche



  • Hallo zusammen,

    ich frage mich, ob man die Sprungsuch in eine Komplexitätsklasse einordnen kann. Diese funktioniert so: Ich durchspringe ein sortierters Array mit einer gewissen Sprungbreite. Sobald das aktuelle Element größer als das gesuchte ist, durchsuche ich nur noch das letzte Intervall mit einem Suchalgorithmus. Hierbei kann die ineffiziente Sequentialsuche oder die Binärsuche eingesetzt werden.

    - Lässt sich eine Komplexität für die Sprungsuche bestimmen oder hängt die vom Suchalgorithmus ab, den ich für das eine Intevall wähle?

    - Warum soll die Sprungweite gerade die Wurzel aus n sein, wenn n die Arraylänge ist?

    Vielen Dank
    lg, freakC++



  • Größe des sortierten Arrays sei n.
    Sprungweite sei x.

    Ich muß maximal n/x mal groß Springen. Und danach maximal x mal einen Einersprung machen.

    Gesamtzahl der Sprünge: n/x+x

    Bei welchem s ist das minimal?
    Ist eine Extremwertaufgabe wie damals beim Abi.

    f(x)=n/x+x

    f'(x)=1-n/x²
    http://www.wolframalpha.com/input/?i=n%2Fx%2Bx

    f'(x)=0 (!)
    x=sqrt(n)
    http://www.wolframalpha.com/input/?i=1-n%2Fx^2%3D0



  • freakC++ schrieb:

    - Lässt sich eine Komplexität für die Sprungsuche bestimmen oder hängt die vom Suchalgorithmus ab, den ich für das eine Intevall wähle?

    Hängt natürlich davon ab.
    Nehme ich fürs kleine Intervall auch linare Suche, ist Sprungweite sqrt(n) optimal mit Laufzeit=sqrt(n)+sqrt(n) Sprüngen.

    Nehme ich fürs kleine Intervall binäre Suche, ist Sprungweite n/2 optimal mit Laufzeit=1+ld(n/2) Sprüngen.

    Nehme ich fürs kleine Intervall eine sehr langsame Suche(1), ist Sprungweite 1 wohl optimal mit Laufzeit=n Sprüngen.

    (1) zum Beispiel slowsort oder bogosort gefolgt von binärer Suche



  • Das leuchtet ein. Vielen Dank, ich bin auch auf die Wurzel n gekommen.

    volkard schrieb:

    Ich muß maximal n/x mal groß Springen. Und danach maximal x mal einen Einersprung machen.

    Warum muss ich aber noch den letzten Einersprung machen? Mir ist klar, dass ich maximal n/x mal springen muss. Dann wähle ich die Binärsuche und muss nur noch das letzte Intervall durchsuchen. 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?

    lg, freakC++



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


Log in to reply