Por favor alguien puede 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. Escoja cualquier mensaje m y h calcular (m).
2. Actualización de la lista L. Comprobar si h (m) está en la lista L.
3. si (h (m), m) ya está en L, un par mensaje colisión ha sido encontrado. cosa sino el par (h (m), m) en el lista L y volver al paso 1.

A partir de la paradoja del cumpleaños sabemos que podemos esperar encontrar una búsqueda de entrada, después de realizar sobre 2 ^ (n / 2) evaluaciones de patata.

¿El por encima de 2 iteraciones medias ^ (n / 2) a través de los anteriormente bucle entero (es decir, 2 ^ (n / 2) vuelve a la etapa 1), o significa 2 comparaciones ^ (n / 2) a los elementos individuales ya en L?

Answer 1

Significa 2 ^ (n / 2) iteraciones a través del bucle. Pero tenga en cuenta que L no sería una lista de lo normal aquí, pero un mapeo h(m) tabla hash para m. Así cada iteración solo necesitaría un número constante (O (1)) de las comparaciones en promedio, y no habría O (2 ^ (n / 2)) comparaciones en total.

Si L había sido una matriz normal o una lista enlazada, a continuación, el número de comparaciones sería mucho mayor, ya que tendría que buscar a través de toda la lista de cada iteración. Esta sería una mala manera de implementar este algoritmo sin embargo.