Kann jemand bitte den Geburtstagseffekt für mich klären?

Question

Bitte helfen Sie den Geburtstags-Effekt zu interpretieren, wie in Wikipedia beschrieben:

Ein Geburtstag Angriff funktioniert wie folgt:

1. jede Nachricht m-Auswahl und berechnen h (m).
2. Liste aktualisieren L. Prüfen, ob h (m) in der Liste L ist.
3. Wenn (h (m), m) bereits in L ist, wurde ein kollidierendes Nachrichtenpaar gefunden. sonst das Paar (h (m), m) speichert in der Liste L und gehen Sie zurück 1.en

Vom Geburtstagsparadoxon zu Schritt wissen wir, dass wir einen passenden Eintrag finden erwarten können, nach der Durchführung über 2^(n/2) Hash-Bewertungen.

funktioniert das obige Mittelwert 2^(n/2) Iterationen durch die obige gesamte Schleife (dh 2^(n/2) kehrt zu Schritt 1), OR bedeutet es 2^(n/2) Vergleiche zu einzelnen Gegenständen bereits in L?

Answer 1

Es bedeutet 2^(n/2) Iterationen durch die Schleife. Beachten Sie jedoch, dass L hier keine normale Liste ist, sondern eine Hashtabellenzuordnung h(m) zu m. Somit würde jede Iteration nur eine konstante Anzahl (O (1)) von Vergleichen im Durchschnitt benötigen, und es würde insgesamt O (2^(n/2)) Vergleiche geben.

Wenn L ein normales Array oder eine verknüpfte Liste gewesen wäre, wäre die Anzahl der Vergleiche viel größer, da Sie jede Iteration durch die gesamte Liste durchsuchen müssen. Dies wäre jedoch eine schlechte Möglichkeit, diesen Algorithmus zu implementieren.