يمكن للشخص يرجى توضيح عيد ميلاد تأثير بالنسبة لي ؟

Question

الرجاء المساعدة تفسير ميلاد تأثير كما هو موضح في ويكيبيديا:

عيد ميلاد الهجوم يعمل على النحو التالي:

1. اختيار أي رسالة م وحساب h(m).
2. تحديث قائمة L.تحقق مما إذا كان h(m) هو في قائمة L.
3. إذا (ح) م (،م) هو بالفعل في لتر من الاصطدام رسالة زوج وجد.آخر حفظ الزوج (ح) م (،م) في قائمة L والعودة إلى الخطوة 1.

من مفارقة عيد ميلاد ونحن نعلم أننا يمكن أن نتوقع أن تجد مطابقة الدخول عن بعد تنفيذ 2^(ن/2) تجزئة التقييمات.

هل ما سبق يعني 2^(ن/2) التكرارات من خلال فوق كامل حلقة (أي2^(ن/2) ترجع إلى الخطوة 1) ، أو يعني 2^(ن/2) المقارنات الفردية البنود بالفعل في ل ؟

Answer 1

يعني 2^(ن/2) التكرارات خلال الحلقة.ولكن لاحظ أن L لن تكون طبيعية قائمة هنا ، ولكن جدول تجزئة الخرائط h(m) إلى m.لذلك كل التكرار سوف تحتاج فقط عدد ثابت (O(1)) من المقارنات في المتوسط ، و لن يكون هناك س(2^(ن/2)) مقارنات في المجموع.

إذا كنت طبيعي مجموعة أو قائمة مرتبطة ، ثم عدد من المقارنات ستكون أكبر كثيرا منذ كنت في حاجة إلى البحث من خلال قائمة كاملة كل التكرار.هذا من شأنه أن يكون وسيلة سيئة تنفيذ هذه الخوارزمية على الرغم من.