بالنظر إلى قائمة غير مسبوومة ببنود $ N $، كم عدد المقارنات العشوائية اللازمة في المتوسط لتكون قادرة على فرز القائمة؟

Question

هناك قائمة غير مصنفة من $ n $ العناصر $ x_1، \ Ldots، x_n $ . حتى تتمكن من فرز القائمة، فإنك تعطى واحدة من $ {n \ اختر 2} $ مقارنات ثنائية محتملة بشكل موحد عشوائيا (مع استبدال).

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

بعض أسئلة المتابعة:

1. ماذا يشبه التوزيع لعدد المقارنات؟
2. ما هي الإجابة إذا كنت تستخدم $ K $ - مقارنات الأرض بدلا من تلك الثنائية.
3. ما هي الإجابة إذا تم إجراء المقارنات دون استبدال (I.E. ألا تحصل على نفس المقارنة مرتين)؟
4. نظرا لمجموعة من المقارنات، كيف يمكن للتحقق من المرء ما إذا كانت القائمة فرز قادرة؟ أنا تقريبا معينة من الإجابة هي إنشاء فرز DAG و Topological، لكنني أريد فقط أن أؤكد.

جوابة ISH الدقيقة ستكون لطيفة، ولكن $ O $ الإجابة على ما يرام، أفترض.

Answer 1

من غير ذلك، ستحتاج إلى $ \ theta (n ^ 2 \ log n) $ المقارنات.

افترض $ x _ {(1)}، \ Dots، x _ {(n)} $ يدل على العناصر الموجودة في الترتيب الفرز. ثم إذا كنت لا ترى مقارنة بين $ x _ {(1)} $ و $ x _ {(2)} $ ، لن يكون لديك طريقة لمعرفة النظام الذي يجب أن تظهر فيه. وينطبق الشيء نفسه على كل زوج من العناصر المجاورة. لذلك، هناك $ n-1 $ coupons (واحد لكل زوج من العناصر المجاورة)، وتحتاج إلى جمعها جميعا. بناء على مشكلة جامع القسيمة ، ونحن نعلم أنك ستحتاج إلى $ \ Theta (n \ log n) $ كوبونات مختارة عشوائيا قبل جمعها جميعا. كل ملاحظة لديها 2 دولار أمريكي $ فرصة كونها قسيمة، لذلك في المجموع سنحتاج إلى $ \ theta (n ^ 2 \ Log N) ملاحظات $ قبل جمع جميع القسائم. إذا نجمع كل القسائم، فيمكننا فرز $ x $ 's؛ إذا فقدت أي قسيمة، لا يمكننا فرزها.

الأسئلة اللاحقة تغلي الحقائق حول مشكلة جامع القسيمة، ويمكنك استخدام حدود الذيل على Wikipedia لتحمل المعلومات حول التوزيع.

إذا تم اختيار المقارنات دون استبدال، فأنت بحاجة إلى $ \ theta (n ^ 2) $ الملاحظات.

طريقة معقولة للتحقق مما إذا كانت القائمة قابلة للتصنيع هي القيام بفرز طوبولوجي، ثم تحقق من أنك لاحظت مقارنة بين كل زوج من العناصر المجاورة في الترتيب المصنوع من علمولوجيا.