AlgoVerse

انتخاب با میانه‌ی میانه‌ها

k-امین عنصر کوچک را در بدترین حالت هم در زمان خطی پیدا می‌کند: محور، میانه‌ی میانه‌های گروه‌های پنج‌تایی است.

Quickselect به‌طور میانگین خطی است، ولی اگر محورها بد باشند به O(n²) می‌رسد. میانه‌ی میانه‌ها (بلوم، فلوید، پرت، ریوست و تارجان، ۱۹۷۳) محوری انتخاب می‌کند که همیشه خوب است:

ادامه‌ی توضیح ↓
ورودی:
n=17 · k=4خروجی PDF

هفده عدد؛ چهارمین عدد کوچک را می‌خواهیم. محور اول ۱۲ است، جواب در بخش کوچک‌تر است و محور دوم، ۵، خود جواب است.

  1. def select(a, k):
  2. # The k-th smallest item (k = 1 is the minimum), in worst-case linear time.
  3. if len(a) <= 5:
  4. a = sorted(a)
  5. return a[k - 1]
  6. groups = [sorted(a[i:i + 5]) for i in range(0, len(a), 5)]
  7. medians = [g[(len(g) - 1) // 2] for g in groups]
  8. pivot = select(medians, (len(medians) + 1) // 2)
  9. low = [x for x in a if x < pivot]
  10. high = [x for x in a if x > pivot]
  11. same = len(a) - len(low) - len(high)
  12. if k <= len(low):
  13. return select(low, k)
  14. if k <= len(low) + same:
  15. return pivot
  16. return select(high, k - len(low) - same)

ناوردا: k-امین عنصر کوچکِ آرایه‌ی اصلی همیشه k-امین عنصر کوچکِ آرایه‌ی فعلی است (با k به‌روزشده).

شروع اجرا

120312527318430516227981592710511201211131414215816

درخت فراخوانی‌های بازگشتی

4

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

k4

نارنجی = در همین گام عوض شد

a list

123257183012291527520111428

Call stack

  1. select()خط 1
گام ۱ از ۲۹
خط سیاه = pivot · خط نارنجی = گام کلیدیmedians: 0/2 · small: 0/2 · pivot: 0/2 · split: 0/2 · found: 0/1 · go_low: 0/1
    توضیح

    ایده

    Quickselect به‌طور میانگین خطی است، ولی اگر محورها بد باشند به O(n²) می‌رسد. میانه‌ی میانه‌ها (بلوم، فلوید، پرت، ریوست و تارجان، ۱۹۷۳) محوری انتخاب می‌کند که همیشه خوب است:

    1. آرایه را به گروه‌های ۵تایی تقسیم کن و میانه‌ی هر گروه را پیدا کن.
    2. با فراخوانی بازگشتی، میانه‌ی همین میانه‌ها را پیدا کن: این محور است.
    3. آرایه را به کوچک‌تر، برابر و بزرگ‌تر از محور تقسیم کن و فقط در بخشی که جواب در آن است ادامه بده.

    چرا خطی؟

    دست‌کم نیمی از گروه‌ها میانه‌ای ≥ محور دارند و در هر کدام دست‌کم ۳ عنصر ≥ محورند؛ پس حدود 3n/10 عنصر بزرگ‌تر و 3n/10 کوچک‌تر از محورند و هر بخش حداکثر 7n/10 است:

    T(n) ≤ T(n/5) + T(7n/10) + O(n)  ⇒  T(n) = O(n)

    چون 1/5 + 7/10 < 1.

    در trace به چه چیزی نگاه کنی

    • میله‌ها آرایه‌ی فراخوانی فعلی‌اند؛ ببین هر بار چقدر کوچک‌تر می‌شود.
    • درخت فراخوانی‌ها دو نوع فراخوانی دارد: یکی برای میانه‌ها و یکی برای بخشی که جواب در آن است.