فرز سريع مقابل راديكس فرز
-
29-09-2020 - |
سؤال
في امتحان ترميز، طلبت ذات مرة هذا السؤال:
على افتراض أنك فقط فرز الأعداد الصحيحة في ترتيب تصاعدي، أي الخوارزمية التي تستخدمها عندما تريد إعطاء الأولوية للسرعة أكثر، ولكنك ترغب أيضا في توفير المساحة؟
الخيارات كانت:
- lsd radix فرز
- دمج فرز
- فرز سريع
أعتقد أنه يمكن إجراء حجة بين LSD راديكس فرز و QuickSort .
راديكس فرز سيعمل في $ o (kn) $ و QuickSort سيعمل في $ O (n \ log n) $ وأسوأ الحالات، $ O (n ^ 2) $
اخترت راديكس فرز كإجابة، لكنني فضولي حول ما كان عليه الآخر أن يقول.
المحلول
هذا يعتمد ... إذا كان عدد أرقام الإدخال $ n $ ، على افتراض نموذج Word-RAM للحساب، وحجم كلمة $ \ theta (\ log n) $ بت، وأسوأ الحالات المدخلات:
-
سيتطلب فرز
-
radix $ O (n \ log n) $ الوقت و $ O (n) $ المساحة المساعدة.
-
quicksort مع التحديد المحوري الثابت أو العشوائي سيتطلب $ O (n ^ 2) $ وقت الأحوال الأسوأ و $ o (\ log n) $ المساحة المساعدة.
-
mergesort يتطلب $ O (n \ log n) $ الوقت و $ o (n) / تمتد> المساحة المساعدة.
راديكس فرز ودمج الفرز ثم ما يعادلها في هذا الإعداد.
لاحظ أن استخدام QuickSort مع اختيار تحديد Pivoit عشوائي في وقت التعقيد من $ O (n \ log n) $ مع احتمال كبير. اختيار المحور المحدد في الطريقة التي تقسم العناصر على مجموعتين في مجموعتين تمنحها كعامل ثابت بصرف النظر عن خوارزمية مع أسوأ حالة التعقيد $ O (n \ log n) $ و $ o (\ log n) $ المساحة الإضافية.