احتمال این که در مرتب سازی سریع تصادفی(random) پیچیدگی برابر n به توان دو بشه چقدره؟
سلام. به نظرم سؤال نسبتاً سختیه ولی مفیده.
یک راهکار که شاید جواب بده اینه که نسبت جایگشت‌هایی که این حالت رو ایجاد می‌کنند، به کل !n جایگشت بدست بیارید. در این مرتب‌سازی بدترین حالت وقتیه که پارتیشن‌ها (افرازهای دوتایی) در تمام مراحل بدترین (یعنی ۰ به n-1) باشند. پس مسئله‌ی اصلی شما میشه این:
تعداد اعضای خانواده‌ای از جایگشت‌های n عنصری را بشمارید که، با فرض احتمال انتخاب به عنوان محورِ برابر برای همه‌ی عناصر، در قریب به اتفاق مراحلِ Quick Sort بدترین پارتیشن را ایجاد می‌کنند.
• در مورد محاسبه‌پذیری خانواده‌ی مذکور یا لااقل کارآیی اون شدیداً مرددم؛ احتمالاً راهکار بهتری وجود داره.
• دقت کنید که حتی پارتیشن‌هایی مثل ۱ به n-2 هم بدترین حالت رو ایجاد نخواهند کرد: (O(nlgn.
• مسئله‌ی Randomize بودن در فرض احتمال یکنواخت لحاظ شده.
• مفهوم "قریب به اتفاق" باید دقیقاً مشخص بشه. مثلاً در CLRS بیان شده که اگر پارتیشن‌ها مرحله در میان بهترین و بدترین باشند هم: (O(nlgn.
• اگر فکر می‌کنی پایه‌ای مشکل داری، با فصل مرتب‌سازی سریع CLRS (فصل ۷ در ویرایش سوم) می‌تونی آشنایی کلی پیدا کنی با این مباحث؛ هرچند که به نظر راه حل مسئله‌ی شما در اونجا بیان نشده.
امیدوارم کمک کرده باشم. و من الله التوفیق . . .