Hashtabelle < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 21:33 Mi 04.06.2008 | | Autor: | Wimme |
| Aufgabe | Folgende Strategie zum Wachsen einer Hashtabelle:
Bei einem Belegungsfaktor [mm] \alpha [/mm] =0.75 wird die Größe der Tabelle verdoppelt, und alle Elemente werden in die neue Hashtabelle mittels elementarer Einfüge-Operationen neu eingehasht. Ausgangspunkt Tabelle der Größe 1. Eine elementare Einfüge-Operation fasst zusammen: Anw. Hashfunktion, alle Sondierungsschritte und das Einfügen des Ergebnisses.
Zeigen Sie, dass n Einfüge Operationen in eine solche dynamische Hashtabelle nur O(n) elementare Einfüge Op brauchen! |
Ich habe erstmal eine Tabelle zu dem Problem erstellt, wie es auch vorher gefordert war:
k Elemente mit Hilfe des Verfahrens von 1 bis 12.
[mm] \vmat{ k & \mbox{Größe} & \mbox{Elem.Op}\\1 & 2 & 2\\ 2 & 4 &3 \\ 3 & 8 & 4\\ 4 & 8 & 1\\ 5 & 8 & 1\\6 & 16 & 7\\7 & 16 & 1\\8 & 16 & 1\\9 & 16 & 1\\10 & 16 & 1\\11 & 16 & 1\\12 & 32 & 13\\}
[/mm]
So, wie gehe ich jetzt daran ran? Was mir an der Tabelle schon mal auffällt, ist, dass die Blöcke mit 1.El.Op immer größer werden, genauer doppelt so groß. Bei einem "Sprung" brauche ich k+1 Operationen. Wie kann ich das jetzt ausnutzen um das Einfügen von n Elementen zu beschreiben? Gibt es ld(n) viele Blöcke? Aber ich will ja auf O(n) kommen.
Danke für jede Hilfe!
Wimme
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Fr 06.06.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
