Time and Space Complexity

تعقيد الوقت:

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

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

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

ملخص:

• يعتبر الفرز السريع (Quick Sort) سريعًا جدًا في المتوسط وهو خوارزمية فرز أساسية في الممارسة العملية.
• يمكن أن يؤدي اختيار المحور السيئ إلى تدهور الأداء إلى O(n²)؛ بينما تتجنب استراتيجيات المحور الجيدة (مثل اختيار عنصر عشوائي أو الوسيط) ذلك.