[FRAGE] - Laufzeitberechnung beim lin Sondieren/^2 Sondieren
Results 1 to 7 of 7
  1. #1
    Heavy's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Posts
    1,340
    Thanks
    2
    Thanked 5 Times in 2 Posts

    Laufzeitberechnung beim lin Sondieren/^2 Sondieren

    Also ich versteh die Beispiele im Skriptum wie diese Sondierverfahren ungefähr funktionieren.
    Nur kann ich die Laufzeit nicht berechnen, wie komm ich auf das n beim alpha?
    Außerdem wie find ich heraus ob die Suche erfolgreich oder erfolglos ist?
    Könnte jemand ein Beispiel für eine erfolglose Suche angeben?
    Religion ist ein Glaube,
    Wissenschaft als Teilgebiet ist ein Glaube,
    die Wahrheit liegt in der Gegenwart des Menschen.

  2. #2

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also, im Skriptum steht bei den Laufzeiten für diese beiden Algorithmen "ohne Beweis", i.e. ausrechnen werden wie sie bestimmt nicht können müssen. Das gestaltet sich nämlich ziemlich schwierig.

    Jedenfalls ist das alpha = n/m, wobei n die Elemente, die auf denselben Platz in der Hashtabelle abgebildet werden (würden), und die m die Anzahl der Plätze in der Tabelle ist. Beim Lin. Sondieren und quadratischen Sondieren muss das <= 1 sein, da ja außerhalb der Tabelle nix gespeichert werden kann.

    Eine erfolglose Suche ist, wenn du das gesuchte Elemente nicht findest

    Allerdings kanns dabei natürlich sein, dass das nicht vorhandene Element von der Hash Funktion auf einen Platz abgebildet wird, wo schon ein anderes steht und auch die folgenden Plätze belegt sind (in der Sondierungsreihenfolge), d.h. möglicherweise gehst du dann noch ziemlich viele Elemente durch, ehe du feststellst, dass das Element gar nicht da ist!

  3. #3
    Heavy's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Posts
    1,340
    Thanks
    2
    Thanked 5 Times in 2 Posts
    Darüber hab ich gestern ein paar Stunden lang den Kopf zerbrochen wie ich das n herausfinden könnte...
    Ok danke dass du mich darauf hingewiesen hast, sonst hätt ich mir weiter das unnötige gelernt.
    Religion ist ein Glaube,
    Wissenschaft als Teilgebiet ist ein Glaube,
    die Wahrheit liegt in der Gegenwart des Menschen.

  4. #4
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    imho steht das n für die Gesamtanzahl der Elemente, die auf einer Tabelle mit der Größe m abgelegt werden sollen.

    alpha ist demnach die durchschnittliche Anzahl der Elemente pro Tabellenplatz (bei Verkettung der Überläufer) (bei anderen Hashverfahren gibts gleichzeitig den der belegten Felder aus)

    lg steve
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  5. #5
    #!/usr/bin/perl's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Posts
    291
    Thanks
    0
    Thanked 1 Time in 1 Post
    Original geschrieben von steve
    imho steht das n für die Gesamtanzahl der Elemente, die auf einer Tabelle mit der Größe m abgelegt werden sollen.
    denk ich auch, sonst muesste \alpha nicht immer <= 1 sein. Und mehr Elemente einfuegen als die hashtable gross is spielts nicht, also m >= n und alpha = n/m <= 1
    this is Unix land. In silent nights, you can hear Windows machines reboot...

  6. #6
    Heavy's Avatar
    Title
    Dipl.Ing
    Join Date
    Feb 2002
    Posts
    1,340
    Thanks
    2
    Thanked 5 Times in 2 Posts
    Kommt das jetzt zum Test oder nicht?
    Wenn nicht dann vergess ich das ganz schnell.

    Weiss außerdem jemand wie ich auf das i komme?
    Soll ich bei i jedesmal von 1...m-1 durchprobieren bis ich eine freie Stelle gefunden hab?
    Jaja ich weiss ich bin in AlgoDat absolut eine Niete.
    Religion ist ein Glaube,
    Wissenschaft als Teilgebiet ist ein Glaube,
    die Wahrheit liegt in der Gegenwart des Menschen.

  7. #7

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    i ist nur der "Sondierindex" und läuft von 0 an, bis du eine freie Stelle gefunden hast, sorry, schneller geht das nicht, wenns mit i=0 nicht frei ist, dann musst du halt mit 1, dann mit 2, dann mit 3 etc.. probieren, bis eine freie Stelle da ist, das kann sich schon ziehen. Bei einem PO Beispiel mit Double Hashing musste ich grad bis i=6 rechnen

    Mitm alpha hab ich mich geirrt, sorry... das ist natürlich Anzahl ALLER Elemente in der Tabelle / Tabellenplätze

    Allerdings können z.b. bei Hashtabellen mit verketteten Überläufern schon mehr als m Elemente in der Tabelle sein, weil man ja auch "aus der Tabelle rausschreiben" kann, bei Offenen Hashverfahren aber natürlich nicht!

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •