Algorithmen[5]#3

[Thomas]

kann mir jemand bei der aufgabe helfen?
um ein sortieren in klogk möglich zu machen muss man ja die gleichen schlüssel zusammen fassen. würde gehen mit einer hash-funktion die die werte dann in eine tabelle mit verketteten listen einfügt. dafür bräuchte man aber eine perfekte hash-funktion, da man ja über die werte der schlüssel gar nichts weiß und wirklich nur die gleichen werte an der selben tabellenstelle eingefügt werden dürfen. jetzt frag ich mich ob man einfach sagen könnte man benutzt eine perfekte hash-funktion? oder kann man iwie von den schlüsseln zurück auf die werte kommen mit einer vllt durch die schlüsel dann gegebenen funktion? hat da jemand ne idee oder vllt ne möglichkeit dass besser

[Tankwart]

Die Hashfunktion muss ja nicht perfekt sein, das hieße ja dass die Werte gleichmäßig verteilt sind, das ist aber egal, hauptsache gleiche Schlüssel im gleichen Feld.
Ich hab einfach die Schlüssel auf einen Array abgebildet mit A[key] und dann konkateniert, im Buch steht dazu nämlich

The total execution time T is O(n) for setting up the buckets and concatenating
the sorted buckets, plus the time for sorting the buckets.

(S.118).

Mit Quicksort des entstandenen Arrays kommt man dann auf O(n+k log k). Wahrscheinlich bezieht sich das oben gennante Zitat nur auf den Durchschnittsfall oder sowas, hab aber keine Ahnung wie das sonst gehen sollte, wenn |k| != k .

[Thomas]

wie meinst du das? du hast ein array erstellt der größe x, also dem größten möglichen key und dann die keys jeweils in dem passenden feld gespeichert? das hab ich mir auch überlegt. aba was meinst du dann mit konkatenieren? die leeren felder weglassen, damit nur die vollen k felder übrig bleiben oda wie?

[Chrisss]

naja wenn du ne folge mit der leeren folge <> konkatenierst passiert ganz einfach nich viel würd ich mal sagen ;P
allerdings ist in der aufgabenstellung von einem sehr großen Universum die rede, das ich eigentlich so interpretiere dass dieses n in der größenordnung von millionen liegt (oder noch größer), womit das ganze auf diese weise in lächerlichem speicherplatz-verbrauch ausarten würde.
also wäre es schon sinnvoll dass diese schlüsselfunktion nur auf werte im bereich 1 bis k abbildet. Aber ob das so einfach machbar ist?

[Thomas]

also wenn ichs heute im tutorium richtig verstanden habe macht man sowas immer mit einer universellen hash-funktion indem man sagt h sei eine zufällige hash-funktion. h bildet dann gleiche schlüssel immer auf gleiche werte ab, aber eben nur die gleichen schlüssel. wodurch man dann nur k verschiedene werte erhält. so wurde übrigens auch die erste aufgabe des letzte übungsblattes gelöst, in dem man die menge hasht und dann für jedes paar (a,b) überprüft ob auch das paar (b,a) gehasht wurde und find eben in O(1) liegt für universelle hash-funktionen. so müsste es hier dann auch gehen dass man mit einer universellen hash-funktion hasht und dann ein array mit verketteten listen mit k-einträgen erhält und das dann mit einem sortieralgorithmus sortieren kann.
zum sortieren dann merge-sort benutzen und man hat ne Laufzeit von O(n + k log k)