Кто-то может разъяснить Эффект Дня рождения для меня?
Помогите интерпретировать эффект Дня рождения, как описано в Википедии:
Нападение дня рождения работает следующим образом:
- Выберите любое сообщение m и вычислите h (m).
- Список обновления L. Проверьте, находится ли h (m) в списке L.
- если (h (m), m) уже находится в L, сталкивающаяся пара сообщения была найдена. еще сохраните пару (h (m), m) в списке L, и вернитесь к шагу 1.
От парадокса дня рождения мы знаем, что можем ожидать находить запись соответствия после выполнения о 2^ (n/2) оценки хеша.
Вышеупомянутое означает 2^ (n/2) повторения через вышеупомянутый весь цикл (т.е. 2^ (n/2) возвращается к шагу 1), ИЛИ это означает 2^ (n/2) сравнения с отдельными объектами уже в L?
1 ответ
Это означает 2 ^ (n / 2) итераций в цикле. Но обратите внимание, что L здесь не будет обычным списком, а будет отображением хэш-таблицы h (m) в m . Таким образом, для каждой итерации потребуется только постоянное число (O (1)) сравнений в среднем, и всего будет O (2 ^ (n / 2)) сравнений.
Если бы L был обычным массивом или связанным списком, то количество сравнений было бы намного больше, поскольку вам нужно было бы перебирать весь список на каждой итерации. Однако это был бы плохой способ реализовать этот алгоритм.