یافتن میانه بدون مرتب‌سازی کامل: الگوریتم‌های انتخاب زمان-خطی

مسئله انتخاب

i-امین آمار ترتیبی یک مجموعه از n عنصر، صرفاً i-امین کوچک‌ترین عنصر در آن مجموعه است. Selection Problem (مسئله انتخاب) می‌پرسد: با داشتن یک آرایه مرتب‌نشده و یک ایندکس i، آمار ترتیبی i-ام را پیدا کن. موارد خاص شامل یافتن حداقل (i = 1)، حداکثر (i = n)، و میانه (i = ⌈n/2⌉) است.

یک رویکرد ساده ابتدا آرایه را مرتب می‌کند، با استفاده از یکی از الگوریتم‌های Θ(n log n) که پیش‌تر در این مجموعه بحث شد، سپس صرفاً به نتیجه مرتب‌شده ایندکس می‌زند. این کار می‌کند اما کار بیشتری از نیاز انجام می‌دهد — مرتب‌سازی مسئله‌ای اساساً سخت‌تر از یافتن یک آمار ترتیبی خاص را حل می‌کند. این مقاله الگوریتم‌هایی که انتخاب را مستقیماً حل می‌کنند، بدون مرتب‌سازی کامل، پوشش می‌دهد.

یافتن حداقل یا حداکثر: یک پیمایش خطی بدیهی

یافتن هرکدام از حداقل یا حداکثر به‌تنهایی فقط نیازمند یک عبور واحد در سراسر آرایه است، که هر عنصر را با کاندید فعلی مقایسه می‌کند.

MINIMUM(A, n):
  min = A[1]
  برای i = 2 تا n:
      اگر A[i] < min:
          min = A[i]
  min را برگردان

این واضحاً در زمان Θ(n) اجرا می‌شود، و اثبات بهینه‌بودن آن آسان است: هر الگوریتمی که حداقل را پیدا می‌کند باید حداقل یک‌بار هر عنصر را بررسی کند، چون یک عنصر بررسی‌نشده همیشه می‌تواند در نهایت حداقل واقعی از آب دربیاید، که کران پایین متناظر Ω(n) را می‌دهد.

یک پرسش جالب‌تر یافتن هم‌زمان حداقل و حداکثر است. یک رویکرد ساده دو عبور جداگانه انجام می‌دهد، و در مجموع از 2n - 2 مقایسه استفاده می‌کند. یک رویکرد ماهرانه‌تر عناصر را به‌صورت جفتی پردازش می‌کند، ابتدا هر جفت را با یکدیگر مقایسه می‌کند، سپس فقط برنده را با حداکثر فعلی و فقط بازنده را با حداقل فعلی مقایسه می‌کند، و کل را به تقریباً 3n/2 مقایسه کاهش می‌دهد — یک بهبود فاکتور-ثابت معنادار.

انتخاب تصادفی: زمان مورد انتظار خطی

یافتن یک آمار ترتیبی دلخواه i جالب‌تر است. RANDOMIZED-SELECT ایده افرازبندی را از quicksort تصادفی، که پیش‌تر در این مجموعه بحث شد، اقتباس می‌کند، اما با یک تفاوت حیاتی: پس از افرازبندی، فقط به یک سمت بازگشت می‌کند نه هر دو.

RANDOMIZED-SELECT(A, p, r, i):
  اگر p == r:
      A[p] را برگردان
  q = RANDOMIZED-PARTITION(A, p, r)
  k = q - p + 1   // تعداد عناصر در سمت پایین، شامل محور
  اگر i == k:
      A[q] را برگردان         // محور دقیقاً پاسخ است
  در غیر این صورت اگر i < k:
      RANDOMIZED-SELECT(A, p, q - 1, i) را برگردان   // فقط چپ بازگشت کن
  در غیر این صورت:
      RANDOMIZED-SELECT(A, q + 1, r, i - k) را برگردان // فقط راست بازگشت کن

از آنجا که الگوریتم فقط به یک سمت افراز بازگشت می‌کند نه هر دو، از کار بازگشتی اضافه‌ای که هزینه کل quicksort را Θ(n log n) کرد اجتناب می‌کند. از نظر شهودی، این اندازه مسئله را در هر گام نصف (یا بیشتر) می‌کند در حالی که فقط کار افرازبندی Θ(n) در گام فعلی انجام می‌دهد، نه کار Θ(n) در هر سطح همان‌طور که quicksort در سراسر هر دو شاخه انجام می‌دهد.

تحلیل زمان اجرای مورد انتظار

با استفاده از همان سبک تحلیل احتمالاتی که پیش‌تر در این مجموعه بحث شد، می‌توان نشان داد زمان اجرای مورد انتظار برآورده می‌کند:

از آنجا که محور به‌طور تصادفی انتخاب می‌شود، در امید ریاضی
افراز تقریباً به‌طور یکنواخت تقسیم می‌شود، که یک
رابطه بازگشتی تقریباً می‌دهد:

E[T(n)] ≤ E[T(n/2)] + O(n)

حل این رابطه بازگشتی، مشابه در شکل با
حالت ۲ روش استاد که پیش‌تر در این مجموعه بحث شد:

E[T(n)] = O(n)

یک استخراج دقیق‌تر، که همه تقسیم‌های افراز ممکن وزن‌دهی‌شده با احتمال‌شان را در نظر می‌گیرد، تأیید می‌کند این کران O(n) مورد انتظار صرف‌نظر از مقدار i درخواست‌شده برقرار است، شامل بدترین حالات یافتن حداقل، حداکثر، یا میانه.

مانند quicksort تصادفی، این الگوریتم همچنان یک بدترین‌حالت Θ(n²) دارد — برای مثال، اگر محور تصادفی انتخاب‌شده اتفاقاً به‌طور مکرر کوچک‌ترین یا بزرگ‌ترین عنصر باقی‌مانده باشد — اما این بدترین‌حالت در سراسر انتخاب‌های تصادفی به‌طور ناچیزی نامحتمل است، که الگوریتم را به‌طور قابل‌اعتماد در عمل سریع می‌کند.

انتخاب قطعی: زمان خطی تضمین‌شده

برای اپلیکیشن‌هایی که به یک کران زمان خطی بدترین‌حالت تضمین‌شده نیاز دارند، بدون هیچ وابستگی به تصادفی‌سازی، یک الگوریتم قطعی جزئی‌تر وجود دارد، که اغلب Median-of-Medians (میانه میانه‌ها) نامیده می‌شود. نوآوری کلیدی آن یک روش ماهرانه برای انتخاب یک محور است که تضمین می‌کند یک افراز نسبتاً متوازن تولید می‌کند، صرف‌نظر از اینکه ورودی چگونه باشد.

SELECT(A, n, i):
  اگر n ≤ یک ثابت کوچک (مثلاً 5):
      A را مستقیماً مرتب کن و عنصر i-ام را برگردان
  
  A را به ⌈n/5⌉ گروه از 5 عنصر هرکدام تقسیم کن
  میانه هر گروه را پیدا کن (با مرتب‌سازی هر گروه کوچک)
  به‌طور بازگشتی میانه این ⌈n/5⌉ میانه را پیدا کن — آن را x بنام
  
  A را حول x افراز کن
  فرض کن k = رتبه x در آرایه افرازشده
  اگر i == k:
      x را برگردان
  در غیر این صورت اگر i < k:
      SELECT را به‌طور بازگشتی روی سمت پایین برای عنصر i-ام فراخوانی کن
  در غیر این صورت:
      SELECT را به‌طور بازگشتی روی سمت بالا برای عنصر (i-k)-ام فراخوانی کن

بینش حیاتی این است که میانه-میانه‌ها x تضمین می‌شود از حداقل تقریباً 3n/10 عنصر بزرگ‌تر و از حداقل تقریباً 3n/10 عنصر کوچک‌تر باشد، که تضمین می‌کند افراز هرگز خیلی نامتوازن نباشد، صرف‌نظر از ورودی خاص.

چرا رابطه بازگشتی به زمان خطی حل می‌شود

الگوریتم دو فراخوانی بازگشتی انجام می‌دهد: یکی روی ⌈n/5⌉ عنصر برای یافتن میانه میانه‌ها، و یکی روی حداکثر تقریباً 7n/10 عنصر برای گام اصلی انتخاب بازگشتی، به‌علاوه کار O(n) برای گروه‌بندی، مرتب‌سازی گروه‌های کوچک، و افرازبندی.

T(n) ≤ T(⌈n/5⌉) + T(7n/10) + O(n)

حل این رابطه بازگشتی با استفاده از روش substitution که پیش‌تر در این مجموعه بحث شد، با حدس T(n) ≤ cn:

T(n) ≤ c⌈n/5⌉ + c(7n/10) + O(n)
     ≤ cn/5 + c + 7cn/10 + O(n)
     = 9cn/10 + c + O(n)

این ≤ cn است به‌شرط انتخاب c به‌اندازه کافی بزرگ
که جمله O(n) و +c
توسط باقی‌مانده cn/10 جذب شوند

بنابراین T(n) = O(n)

این تأیید می‌کند الگوریتم میانه-میانه‌ها به زمان اجرای بدترین‌حالت Θ(n) دست می‌یابد — یک تضمین زمان-خطی واقعاً قطعی، برخلاف تضمین زمان-مورد-انتظار الگوریتم تصادفی.

مقایسه دو الگوریتم انتخاب

Randomized Select:
  - زمان مورد انتظار: O(n)
  - زمان بدترین‌حالت: O(n²)، هرچند بسیار نامحتمل
  - پیاده‌سازی ساده، فاکتورهای ثابت کوچک
  - در بیشتر موقعیت‌های عملی ترجیح داده می‌شود

Median-of-Medians (Select قطعی):
  - زمان بدترین‌حالت: O(n)، تضمین‌شده
  - پیاده‌سازی پیچیده‌تر، فاکتورهای ثابت بزرگ‌تر
  - وقتی تضمین‌های بدترین‌حالت ضروری‌اند ترجیح داده می‌شود،
    مانند در سیستم‌های بلادرنگ یا محیط‌های خصمانه

چرا الگوریتم‌های انتخاب فراتر از میانه اهمیت دارند

انتخاب کارآمد کاربردهای عملی در سراسر علوم کامپیوتر دارد: یافتن صدک‌ها در تحلیل آماری، شناسایی k-امین کوتاه‌ترین مسیر در مسیریابی شبکه، و به‌عنوان یک زیرروال درون الگوریتم‌های دیگر، شامل یک نوع استفاده‌شده برای انتخاب محورهای بهتر برای خود quicksort در پیاده‌سازی‌های حساس به کارایی. این واقعیت که این مسئله یک راه‌حل واقعاً زمان-خطی می‌پذیرد، دقیقاً سریع‌تر از کران پایین Ω(n log n) که برای مرتب‌سازی کامل اعمال می‌شود، یک اصل مهم در طراحی الگوریتم را نشان می‌دهد: درک دقیق اینکه یک مسئله واقعاً به چه چیزی نیاز دارد، به‌جای استفاده از آشناترین ابزار، اغلب یک راه‌حل اساساً