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

Question

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

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

1. Выберите любое сообщение m и вычислите h (m).
2. Обновить список L. Проверьте, есть ли h (m) в списке L.
3. если (h (m), m) уже находится в L, обнаружена конфликтующая пара сообщений. иначе сохранить пару (ч (м), м) в перечислите 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 был обычным массивом или связанным списком, то число сравнений было бы намного больше, так как вам нужно было бы искать по всему списку каждую итерацию. Это был бы плохой способ реализовать этот алгоритм.