Qualcuno può chiarire l'effetto di compleanno per me?

Question

Si prega di aiutare a interpretare l'effetto di compleanno, come descritto in Wikipedia:

  

Un attacco di compleanno funziona nel seguente modo:

     

  
1. Scegliere qualsiasi messaggio m e h di calcolo (m).
  
2. Aggiornamento elenco L. Controllare se h (m) è nella lista L.
  
3. se (h (m), m) è già a L, un paio messaggio collisione è stato trovato.   altro che la coppia (h (m), m) nella   lista L e tornare al punto 1.
  

     

Dal paradosso del compleanno sappiamo che possiamo aspettarci di trovare un   contropartita, dopo aver eseguito su   2 ^ (n / 2) valutazioni di hash.

Lo quanto sopra 2 ^ (n / 2) iterazioni medi attraverso i sopra intero ciclo (cioè 2 ^ (n / 2) ritorna al passo 1), o significa 2 ^ (n / 2) confronti ai singoli articoli già a L?

Answer 1

Significa 2 ^ (n 2) / iterazioni del ciclo. Ma nota che L non sarebbe una lista normale qui, ma una tabella hash mappatura h(m) a m. Così ogni iterazione avrebbe solo bisogno di un numero costante (O (1)), di confronti in media, e non ci sarebbe O (2 ^ (n / 2)) i confronti in totale.

Se L fosse stato un allineamento normale o una lista collegata, allora il numero di confronti sarebbe molto più grande in quanto si avrebbe bisogno per la ricerca in tutta la lista ogni iterazione. Questo sarebbe un brutto modo per implementare questo algoritmo però.