میانه میانه‌ها

در علوم رایانه، میانه میانه‌ها یک الگوریتم انتخاب بر پایه الگوریتم انتخاب سریع می‌باشد. این الگوریتم، بهینه و در بدترین حالت ممکن برای انتخاب k امین عضو بزرگ یک مجموعه دارای عملکردی خطی می‌باشد. این الگوریتم میانه تقریبی را در مدت زمانی خطی بدست آورده و به عنوان عنصر محوری در اختیار الگوریتم انتخاب سریع قرار می‌دهد.
این الگوریتم می‌تواند به عنوان یک روش برای پیدا کردن عنصر محوری در مرتب‌سازی سریع مورد استفاده قرار گرفته و به یک الگوریتم مرتب‌سازی بهینه با عملکرد در بدترین حالت از منجر شود. اگرچه این روش بهینه است، اما در عمل برای از بین بردن سربار محاسبه عنصر محوری؛ این عنصر معمولا به صورت تصادفی انتخاب می‌شود. میانه میانه‌ها به عنوان یک بازگشت در الگوریتم انتخاب درونگرا مورد استفاده قرار می‌گیرد تا عملکرد بدترین حالت را بهبود بخشد: انتخاب درونگرا با انتخاب سریع شروع می‌شود تا یک عملکرد متوسط را نتیجه دهد، سپس در صورتی که روند اجرا بسیار کند باشد، از میانه میانه‌ها استفاده می‌کند.
این الگوریتم توسط Blum et al. (1973) منتشر شد و به همین دلیل برخی از مواقع با نام BFPRT (حروف اول اسم ناشران آن) شناخته می‌شود. در مقاله اصلی از این الگوریتم به اسم PICK و از الگوریتم انتخاب سریع به عنواد FIND یاد شده است.
چکیده
زمان لازم برای انتحاب سریع به طور میانگین به صورت خطی رشد می‌کند، اما با انتخاب نامناسب عنصر محوری می‌تواند به صورت درجه دو رشد کند. دلیل این امر این است که انتخاب سریع، یک الگوریتم تقسیم و حل است که هر مرحله آن زمانی از روی باقیمانده اعضا لازم دارد. اگر اندازه مجموعه‌ای که الگوریتم انتخاب سریع روی آن جستجو انجام می‌دهد سریع و به صورت نمایی کاهش یابد (با نسبتی ثابت)، منجر به یک سری هندسی با زمانی از خواهد شد و در نتیجه در طول زمان به صورت خطی رفتار خواهد کرد. حال اگر اندازه این مجموعه با سرعتی آهسته کم شود، مثلا به صورت خطی (در بدترین حالت در هر مرحله تنها یک عضو از مجموعه کاسته می‌شود)، جمع تمامی مراحل منجر به زمانی از خواهد شد. بدترین حالت، زمانی رخ می‌دهد که کوچکترین عضو مجموعه در هر مرحله به عنوان عنصر محوری انتخاب شود (برای مثال حالتی که برای انتخاب بزرگترین عضو یک مجموعه مرتب شده از انتخاب سریع استفاده شود و در هر مرحله اولین عضو مجموعه را به عنوان عنصر محوری در نظر بگیریم).
اگر به صورت پیاپی عناصر محوری خوبی را انتخاب نماییم همواره زمان اجرایی خطی را حتی در بدترین حالت ممکن خواهیم داشت. عنصر محوری خوب، عنصری است که همواره درصد ثابتی از اعضای مجموعه قبل و بعد از آن وجود داشته باشند تا در هر مرحله تعداد اعضای باقیمانده در مجموعه به صورت نمایی کاهش یابد. میانه همیشه یک عنصر محوری خوب محسوب می‌شود (بهترین گزینه برای مرتب‌سازی و یکی از بهترین گزینه‌ها برای انتخاب).
الگوریتم میانه میانه‌ها، میانه را نه به صورت دقیق، بلکه به صورت تقریبی محاسبه می‌کند. اما این تضمین را می‌دهد که مقدار محاسبه شده بین ۳۰امین و ۷۰امین صدک قرار گرفته باشد؛ بنابراین در هر مرحله تعداد داده‌ها حداقل ۳۰٪ کاهش می‌یابد.
الگوریتم
همان‌طور که ذکر شد، میانه میانه‌ها به عنوان یک راه‌حل برای انتخاب عنصر محوری در الگوریتم انتخاب سریع مورد استفاده قرار می‌گیرد و شبه کد آن به صورت زیر است:
function select(list, left, right, n)
if left = right
return left
loop
pivotIndex := pivot(list, left, right)
pivotIndex := partition(list, left, right, pivotIndex)
if n = pivotIndex
return n
else if n
right:
subRight := right
median5 := partition5(list, i, subRight)
swap listmedian5 and list
// compute the median of the n/5 medians-of-five
return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10)
تابع partition5 میانه یک گروه با حداکثر پنج عضو را انتخاب می‌کند. یک راه ساده برای پیاده‌سازی این تابع استفاده از مرتب‌سازی درجی است.
در نهایت می‌توان عمکرد الگوریتم میانه میانه‌ها را به ۵ مرحله تقسیم کرد:
مرحله ۱:
تمامی n عضو به گروه‌های ۵ تایی دسته بندی می‌شوند. (در صورتی که تعداد عضوها به ۵ قابل قسمت نباشد گروه آخر کمتر از ۵ عضو را در خود جای می‌دهد.)
مرحله ۲:
میانه هر یک از گروه‌های ایجاد شده پیدا می‌شوند. (ابتدا هر یک از این گروه‌ها در مرتب شده و سپس میانه آنها انتخاب می‌شود.)
مرحله ۳:
به صورت بازگشتی میانه داده‌ها انتخاب می‌شود.
مرحله ۴:
با استفاده از تابع پارتیشن که میانه انتخابی را به عنوان عنصر محوری در ورودی دریافت می‌کند، با فرض اینکه میانه انتخابی k امین کوچکترین عضو باشد، داده‌ها به دو دسته k - 1 تایی و n - k تایی تقسیم می‌شوند که تمامی اعضای آنها به ترتیب کوچکتر و بزرگتر از میانه انتخابی است.
مرحله ۵:
در این مرحله ۳ حالت وجود دارد:
اگر اندیس میانه انتخابی برابر i باشد: این عضو به عنوان جواب بازگردانده می‌شود.
اگر اندیس میانه انتخابی بزرگتر از i باشد: i امین کوچکترین عضو در بین داده‌های کوچکتر از میانه به عنوان جواب بازگردانده می‌شود.
اگر اندیس میانه انتخابی کوچکتر از i باشد: i - k امین کوچکترین عضو در بین داده‌های بزرگتر از میانه به عنوان جواب بازگردانده می‌شود.
ویژگی‌های عنصر محوری
از گروه‌ها، نیمی از آنها (=×1⁄2) میانه‌هایی کمتر از میانه واقعی (میانه میانه‌ها) و نیمی دیگر از آنها میانه‌هایی بیشتر از آن دارند. در هر یک از گروه‌ها با میانه کمتر از میانه واقعی، ۲ عضو کوچکتر از میانه گروه خود هستند؛ بنابراین در از گروه‌ها حداقل ۳ عضو کوچکتر از میانه اصلی هستند. به صورت مشابه در دیگر از گروه‌ها با میانه بزرگتر از میانه اصلی حداقل ۲ عضو وجود دارند که از میانه گروه خود بزرگتر هستند و در نتیجه از گروه‌ها دارای حداقل ۳ عضو بزرگتر از میانه اصلی هستند؛ بنابراین میانه اصلی حداقل از ×۳ داده‌ها بیشتر و از ×۳ آنها کمتر است؛ بنابراین میانه انتخاب شده بین ۳۰٪ تا ۷۰٪ داده‌ها است:
+ یکی از مراحل روی ۱۰۰ داده تصادفی از ۰ تا ۹۹
۳۹
۷۹
میانه‌ها
۸۳
۸۷
۹۱
عنصر قرمز رنگ: میانه میانه‌ها، عناصر خاکستری: اعداد کوچکتر از میانه میانه‌ها، عناصر سفید: عناصر بزرگتر از میانه میانه‌ها
۵ تایی‌های بالا برای وضوح بیشتر به صورت مرتب شده نمایش داده شده‌اند. اما در واقع، از آنجایی که ما تنها به دنبال میانه این ۵ تایی‌ها هستیم مرتب بودن آنها اهمیتی ندارد.
توجه کنید که تمامی عناصر بالا-راست عنصر قرمز رنگ(۳۰٪ کل عناصر) کوچکتر از آن و تمامی عناصر پایین-چپ این عنصر(۳۰٪ کل عناصر)، بزرگتر از آن هستند.
زمان اجرا
800px
همانطور که در تصویر بالا مشاهده می‌کنید، به جز گروهی که شامل میانه انتخابی (x) است و گروه آخر، در نیمی دیگر از گروه‌ها حداقل ۳ عضو وجود دارد که از x کوچکتر هستند. (این ۳ عضو شامل میانه‌های کوچکتر از x و دو عضو کوچکتر از هر میانه، در هر یک از گروه‌ها است) بنابراین:
\text{elts less than x \geqslant 3(\left \lceil \frac{1{2 \left \lceil \frac{n{5 \right \rceil \right \rceil - 2) \geqslant \frac{3n{10 - 6
به صورت مشابه حداقل 6 - عضو بزرگتر از x هستند. بنابراین مرحله ۵ام حداکثر روی 6 + از داده‌ها بازگشت می‌کند.
از طرفی، مراحل ۱، ۲ و ۴ برای اجرا شدن احتیاج به زمانی از دارند. ( مرحله ۱: ایجاد گروه‌های با ۵ عضو احتیاج به زمانی از دارد، مرحله ۲: مرتب سازی هر گروه ۵ تایی احتیاج به زمانی از و مرحله ۴: تقسیم کردن داده‌ها حول میانه انتخابی احتیاح به زمانی از دارد.) مرحله ۳ زمانی از را احتیاج داشته و مرحله آخر زمانی کمتر از را برای اجرا لازم دارد. با فرض اینکه با n‌های به قدر کافی کوچک زمان اجرا از باشد، میتوان گفت: (n را به دلیلی که مشاهده خواهید کرد حداقل برابر 140 در نظر می‌گیریم)
T(n) \leq \begin{cases O(1), - \text{if n < 140 \\ T(\left \lceil \frac{n{5 \right \rceil)+T(\frac{7n{10 + 6) + O(n), - \text{if n \geq 140 \end{cases
با در نظر گرفتن به عنوان فرض استقرا می‌توان نوشت:
T(n) \leq c \cdot \left \lceil \frac{n{5 \right \rceil + c \cdot (\frac{7n{10 + 6) + an
\Rightarrow T(n) \leq \frac{cn{5 + c + \frac{7cn{10 + 6c + an
\Rightarrow T(n) \leq \frac{9cn{10 + 7c + an
\Rightarrow T(n) \leq cn +(- \frac{cn{10 + 7c + an)
در صورتی که جمله کوچکتر از صفر باشد فرض استقرا برقرار می‌شود و به سادگی میتوان متوجه شد که به ازای
، این جمله کوچکتر از صفر شده و از آنجایی که n از ۱۴۰ بزرگتر است، همواره کمتر مساوی ۲ بوده و به همین دلیل به ازای خواهیم داشت:
T(n) \leq \begin{cases O(1), - \text{if n < 140 \\ O(n), - \text{if n \geq 140 \text{ and c \geq 20a \end{cases