Quelqu'un peut-il s'il vous plaît préciser l'effet anniversaire pour moi?

Question

S'il vous plaît aider à interpréter l'effet anniversaire comme décrit dans Wikipedia:

  

Une attaque d'anniversaire fonctionne comme suit:

     

  
1. Pick tout message m et calculer h (m).
  
2. Liste mise à jour L. Vérifiez si h (m) est dans la liste L.
  
3. if (h (m), m) est déjà en L, une paire de message entrant en collision a été trouvé.   sauver la paire d'autre (h (m), m) dans la   liste L et revenir à l'étape 1.
  

     

Du paradoxe d'anniversaire, nous savons que nous pouvons nous attendre à trouver un   entrée correspondant, après avoir effectué environ   2 ^ (n / 2) les évaluations de hachage.

Est-ce que le dessus de la moyenne 2 ^ (n / 2) itérations à travers les (retourne à l'étape 1 soit 2 ^ (n / 2)), soit que cela signifie 2 ^ comparaisons avec des éléments individuels (n / 2) au-dessus de la boucle entière déjà en L?

Answer 1

Cela signifie 2 ^ (n / 2) itérations dans la boucle. Mais notez que L ne serait pas une liste normale, mais une application table de hachage h(m) à m. Donc, chaque itération aurait seulement besoin d'un nombre constant (O (1)) de comparaisons en moyenne, et il y aurait O (2 ^ (n / 2)) comparaisons au total.

Si L avait été un tableau normal ou une liste chaînée, le nombre de comparaisons serait beaucoup plus puisque vous devrez chercher dans toute la liste chaque itération. Ce serait une mauvaise façon de mettre en œuvre cet algorithme bien.