Worst-Case-Zeit Komplexität der Hashing (Einfügen)

Question

Wenn ich grundlegende Kollisions-Behandlung verwenden, indem Sie den Eingabewert auf den nächsten leeren Steckplatz verlagern, brauche ich nicht n * (n + 1)/2 Treffer insgesamt?

Beispiel:

Eingabe: 0,0,0;

Zugewiesene Größe = 3;

Somit würde es insgesamt 6 Treffer erfordern, um alle drei Werte zuzuweisen.

Ich habe gelesen, dass die Worst-Case-Komplexität ist O (n), aber sollte es nicht O (n^2) dann sein?

Answer 1

Jede Einfügung ist O (1) im Durchschnitt (mit einer guten Hash-Funktion und Resizing-Strategie), aber O (N) im schlimmsten Fall. Also sind N Insertionen im schlimmsten Fall O (N^2).

Answer 2

Es ist O(N) im Durchschnitt.

Es ist in der Tat O(N^2) im schlimmsten Fall.