Kann jemand bitte mir den Geburtstag Effekt erklären?

Question

Bitte Hilfe interpretiert die Wirkung Geburtstag wie in Wikipedia beschrieben:

Ein Geburtstag Angriff funktioniert wie folgt:

1. Wählen Sie jede Nachricht m und Rechen h (m).
2. Update-Liste L. Überprüfen Sie, ob h (m) ist in der Liste L.
3. if (h (m), m) bereits in L ist, ein Kollision Nachrichtenpaar gefunden wurde. sonst rettet das Paar (h (m), m) in der Liste L und gehen Sie zurück zu Schritt 1

Von der Geburtstagsparadox wissen wir, dass wir ein finden erwarten können Passende Eintrag, nach dem Durchführen über 2 ^ (n / 2) hash Auswertungen.

Ist die obige Mittelwert 2 ^ (n / 2) Iterationen durch die oben gesamte Schleife (dh 2 ^ (n / 2) kehrt zu Schritt 1), OR bedeutet es 2 ^ (n / 2) Vergleiche zu einzelnen Posten bereits in L?

Answer 1

Es bedeutet 2 ^ (n / 2) Iterationen durch die Schleife. Aber beachten Sie, dass L würde keine normale Liste sein hier, aber eine Hash-Tabellen-Mapping h(m) zu m. So wird jede Iteration würde insgesamt nur eine konstante Anzahl benötigt (O (1)) von Vergleichen in Durchschnitt und es wäre O (2 ^ (n / 2)) Vergleiche.

Wenn L ein normales Array oder eine verkettete Liste gewesen war, dann die Anzahl der Vergleiche wäre viel größer, da Sie jede Iteration durch die ganze Liste suchen müßten. Dies wäre ein schlechter Weg sein, diesen Algorithmus zu implementieren though.