Может кто-нибудь, пожалуйста, уточнить эффект дня рождения для меня?

Question

Пожалуйста, помогите интерпретировать эффект дня рождения, как описано в Википедии:

Атака на день рождения работает следующим образом:

1. Выберите любое сообщение M и вычислить H (M).
2. Список обновлений L. Проверьте, если H (M) находится в списке L.
3. Если (H (M), M) уже находится в L, была найдена пара коллективных сообщений. иначе сохранить пару (h (m), m) в списке l и вернитесь к шагу 1.

Из парадокса дня рождения мы знаем, что мы можем ожидать, чтобы найти соответствующий ввод, после выполнения около 2 ^ (N / 2) хеш-оценки.

Означает ли вышеизложенное 2 ^ (N / 2) итерации через верхнюю целую петлю (т.е. 2 ^ (N / 2), возвращается к этапу 1), или это означает 2 ^ (N / 2) сравнения для отдельных предметов, уже в л ?

Answer 1

Это означает 2 ^ (N / 2) итерации через петлю. Но обратите внимание L не будет нормальным списком здесь, но отображение хеш-стола h(m) к m. Отказ Таким образом, каждая итерация понадобится только постоянное число (O (1)) сравнения в среднем, и в общей сложности будет (2 ^ (N / 2)).

Если я был обычным массивом или связанным списком, то количество сравнений было бы намного больше, так как вам нужно будет искать по всему списку каждую итерацию. Это было бы плохой способ реализации этого алгоритма.