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

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) сравнения с отдельными элементами, уже находящимися в L?

Answer 1

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

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