59. الخوارزميات الاحتمالية و Randomized Quick Sort

تُدخل الخوارزميات الاحتمالية العشوائية لتحقيق إما أداء متوسط أفضل أو لتبسيط هيكل الخوارزمية. هناك نوعان رئيسيان:

1. خوارزميات لاس فيغاس (Las Vegas Algorithms): تنتج دائماً النتيجة الصحيحة، ولكن وقت تشغيلها عشوائي (مثل Randomized Quick Sort).
2. خوارزميات مونت كارلو (Monte Carlo Algorithms): قد تنتج نتيجة غير صحيحة باحتمالية ما، ولكن وقت تشغيلها حتمي (مثل Bloom Filters، التي تم تناولها في الدرس 30).

Randomized Quick Sort

نعلم أن أسوأ حالة لـ Quick Sort هي O(N²)، والتي تحدث عندما يكون اختيار المحور سيئاً باستمرار.

الحل: بدلاً من اختيار العنصر الأول أو الأخير دائماً كمحور، اختر المحور عشوائياً من المصفوفة الفرعية.

• التأثير: في حين أن أسوأ حالة نظرية تظل O(N²)، فإن احتمال حدوث أسوأ حالة في الواقع يصبح منخفضاً بشكل فلكي. يصبح التعقيد الزمني المتوقع للخوارزمية O(N log N)، بغض النظر عن تنظيم مصفوفة المدخلات.