¿Puede alguien aclarar el efecto de cumpleaños para mí?

Question

Por favor, ayudar a interpretar el efecto de cumpleaños como se describe en Wikipedia:

Un ataque de cumpleaños funciona de la siguiente manera:

1. elegir cualquier mensaje m y calcular h (m).
2. Actualizar lista L. Comprobar si h (m) está en la lista L.
3. si (h (m), m) ya está en L, se ha encontrado un par de mensajes colisionantes. cosa sino la par (h (m), m) en la lista L y volver al paso 1.

Desde la paradoja del cumpleaños sabemos que podemos esperar encontrar una entrada juego, después de realizar aproximadamente 2^(n/2) evaluaciones hash.

Lo anterior significa 2^(n/2) iteraciones a través del bucle completo anterior (es decir, 2^(n/2) regresa al paso 1), O ¿significa 2^(n/2) comparaciones? a artículos individuales que ya están en L?

Answer 1

Significa 2^(n/2) iteraciones a través del ciclo. Pero tenga en cuenta que L no sería una lista normal aquí, sino una asignación de tablas hash h(m) a m. Por lo tanto, cada iteración solo necesitaría un número constante (O (1)) de comparaciones en promedio, y habría O (2^(n/2)) comparaciones en total.

Si L hubiera sido una matriz normal o una lista vinculada, entonces el número de comparaciones sería mucho mayor, ya que necesitaría buscar en toda la lista cada iteración. Sin embargo, esta sería una mala forma de implementar este algoritmo.