Time and Space Complexity

تعقيد الوقت:

• O(d * (n + k))
  • حيث n هو عدد العناصر، وk هو الأساس (10)، وd هو عدد الأرقام في أكبر قيمة. كل تمريرة من d تمريرات تقوم بعمل O(n + k).
• عندما تكون d صغيرة وثابتة، يتصرف هذا مثل O(n)، وهو أسرع من O(n log n) في خوارزميات فرز المقارنة.

تعقيد المساحة:

• O(n + k)
  • تقوم كل تمريرة ببناء مصفوفة مخرجات بحجم n ومصفوفة عد بحجم k.

ملخص:

• فرز الجذر (Radix Sort) هو فرز مستقر وغير معتمد على المقارنة يمكنه التفوق على O(n log n) للمفاتيح الصحيحة ذات عدد محدود من الأرقام.
• يتطلب مفاتيح تنقسم إلى أرقام وبعض الذاكرة الإضافية، ويفترض هذا الإصدار أعداداً صحيحة غير سالبة.