Beweis Komplexität Hashmap

Mathematics
Erstie
Erstie
Beiträge: 17
Registriert: 23. Sep 2013 12:12

Beweis Komplexität Hashmap

Beitrag von Mathematics »

Den Beweis dafür, dass Zugriffe auf Hashmaps im Schnitt konstanten Aufwand haben, habe ich verstanden. Sowohl Wiki als auch Kurzvideo arbeiten hierfür mit Erwartungswert und Quotientenkriterium. Dennoch geht das Wiki davon aus, dass Plätze nicht mehrfach probiert werden ("Ziehen ohne Zurücklegen" bzw. abhängige Ereignisse in der Stochastik), im Video allerdings wird stets wieder dieselbe Wahrscheinlichkeit N/Nmax für bereits belegte Plätze verwendet ("Ziehen mit Zurücklegen" bzw. unabhängige Ereignise in der Stochastik). Beide Ansätze führen über den Erwartungswert und das Quotientenkriterium zur gewünschten Aussage des konstanten Aufwands im Mittel (abhängig nur vom Füllgrad, nicht von der Anzahl der Werte). Da es sich um künstliche Annahmen handelt, lassen sich aber beide gewissermaßen rechtfertigen.
Meine Frage ist nun einfach, welche Version in der Klausur gewünscht wird. Vielleicht meldet sich hierzu ja sogar jemand der Zuständigen?

Zurück zu „Archiv“