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

Question

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

Un attacco di compleanno funziona nel modo seguente:

1. scegliere qualsiasi messaggio m e calcolare h (m).
2. Aggiornamento lista L. Verificare se h (m) è nella lista L.
3. se (h (m), m) è già in L, è stata trovata una coppia di messaggi collidenti. altro salva la coppia (h (m), m) nella lista L e tornare al punto 1.

Dal paradosso del compleanno sappiamo che possiamo aspettarci di trovare una voce corrispondente, dopo aver eseguito circa 2^(n/2) valutazioni di hash.

fa il sopra medio di 2^(n/2) iterazioni attraverso il sopra ciclo intero (cioè 2^(n/2) ritorna al passo 1), o significa 2^(n/2) confronti ai singoli oggetti già in L?

Answer 1

Significa 2^(n/2) iterazioni attraverso il ciclo. Notare che L non sarebbe un elenco normale qui, ma una tabella hash che mappa h(m) a m. Quindi ogni iterazione richiederebbe solo un numero costante (O (1)) di confronti in media e ci sarebbero O (2^(n/2)) confronti in totale.

Se L fosse stato un array normale o un elenco collegato, il numero di confronti sarebbe molto più grande poiché è necessario cercare nell'intero elenco ogni iterazione. Questo sarebbe un cattivo modo per implementare questo algoritmo però.