Zitat von
himitsu:
Tut mir Leid, aber da ist eine Schleife drin, also kann das O(1) nicht stimmen.
Im Worst Case, ja, aber im Durchschnitt interessiert dann doch eher der durchschnittliche Fall
. Und da gilt die angegebene Formel, die in der Quellenangabe auch hergeleitet wird (so viel Wahrscheinlichkeitsrechnung, argh
).
Zitat von
himitsu:
Θarray(n) = Θmap(n / fHashMod) / x
Wenn du Vorfaktoren vergleichen willst, ist asymptotische Laufzeit definitiv das falsche Werkzeug
.