Time and Space Complexity

التعقيد الزمني:

• O(n + k)
  • حيث n هو عدد العناصر و k هو نطاق القيم (الحد الأقصى + 1). تمريرة واحدة للعد، وتمريرة واحدة فوق الأعداد لإعادة البناء.
• عندما تكون k صغيرة وثابتة، يكون هذا فعلياً O(n)، وهو أسرع من O(n log n) في خوارزميات فرز المقارنة.

التعقيد المكاني:

• O(n + k)
  • تستخدم مصفوفة العد O(k) ويستخدم المخرج O(n).

ملخص:

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