Ai đó có thể làm rõ Hiệu ứng sinh nhật cho tôi không?

Question

Xin giúp giải thích các hiệu ứng sinh nhật như mô tả trong Wikipedia:

Một cuộc tấn công sinh nhật hoạt động như sau:

1. Chọn bất kỳ thông điệp m và tính h (m).
2. Danh sách cập nhật L. Kiểm tra xem h (m) có nằm trong danh sách L.
3. nếu (h (m), m) đã có trong L, một cặp thông báo va chạm đã được tìm thấy. khác lưu các cặp (h (m), m) trong danh sách L và quay lại bước 1.

Từ nghịch lý ngày sinh nhật chúng ta biết rằng chúng ta có thể mong đợi để tìm một mục phù hợp, sau khi thực hiện khoảng 2^(n/2) đánh giá băm.

Điều này có nghĩa là 2^(n/2) lặp lại qua toàn bộ vòng lặp trên (tức là 2^(n/2) trở về bước 1), HOẶC có nghĩa là so sánh 2^(n/2) cho từng vật phẩm đã có trong L?

Answer 1

Có nghĩa là lặp lại 2^(n/2) qua vòng lặp. Nhưng lưu ý rằng L sẽ không phải là danh sách bình thường ở đây, nhưng bản đồ bảng băm là h(m) đến m. Vì vậy, mỗi phép lặp sẽ chỉ cần một số hằng số (O (1)) so sánh trung bình, và sẽ có tổng cộng O (2^(n/2)).

Nếu L là một mảng bình thường hoặc danh sách liên kết, thì số lượng so sánh sẽ lớn hơn nhiều vì bạn sẽ cần phải tìm kiếm trong toàn bộ danh sách mỗi lần lặp. Đây sẽ là một cách xấu để thực hiện thuật toán này mặc dù.