Hashing: Ansatzhilfe zu der Aufgabe?
1 Antwort
Zu a): (Achtung: Ich kann nur eine approximierte amortisierte Laufzeit liefern)
Ich hab einfach mal ein paar Annahmen getroffen:
- Ich sage die durchschnittliche Länge eines Wortes sei L.
- Ich sage die Anzahl verschiedener (einzigartiger) Wörter ist u.
- Ich approximiere, dass alle Wörter gleich oft vorkommen, ich also n/u Mal an eine LinkedList anhängen muss.
Das bedeutet, ich muss folgende Sachen in Betracht ziehen:
- Ich muss alle Wörter einlesen. Laufzeit:
- Ich muss jedes Wort einmal komplett hashen. Laufzeit:
- Ich muss approximiert an u Listen jeweils Mal anhängen, und da es u Listen gibt, sind das 2n, also Laufzeit:
Das bedeutet, wenn ich das jetzt asymptotisch aufsummiere, komme ich auf eine approximierte Gesamtlaufzeit von Ich übernehme natürlich keine Garantie, dass das eine korrekte Approximation ist, ich habe sehr viele Sachen einfach angenommen, um es nicht unnötig kompliziert zu machen, aber pseudopolynomiell sieht irgendwie richtig aus.
Zu b):
Das dürfte selbst bei meiner recht halbherzigen Laufzeitanalyse trotzdem aus dieser ersichtlich sein, wie man eine Datei erstellt, die WIRKLICH ätzend ist.
Zu c):
Wenn b) ordentlich gemacht wurde, und das Programm verstanden wurde, ist die Antwort hier trivial.
