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

~7 دقیقه مطالعه · آخرین به‌روزرسانی ۱۶ شهریور ۱۴۰۵

مسئله انتخاب

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) که برای مرتب‌سازی کامل اعمال می‌شود، یک اصل مهم در طراحی الگوریتم را نشان می‌دهد: درک دقیق اینکه یک مسئله واقعاً به چه چیزی نیاز دارد، به‌جای استفاده از آشناترین ابزار، اغلب یک راه‌حل اساساً

نوشته و پژوهش‌شده توسط دکتر شاهین صیامی

مقالات مرتبط

ساختارهای داده ابتدایی: پشته‌ها، صف‌ها، لیست‌های پیوندی، و درخت‌ها

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

ادامه

شکستن مانع n log n: توضیح الگوریتم‌های مرتب‌سازی زمان-خطی

هر الگوریتم مرتب‌سازی مبتنی بر مقایسه در بدترین‌حالت حداقل به زمان Ω(n log n) نیاز دارد، اما الگوریتم‌هایی که کاملاً از مقایسه اجتناب می‌کنند می‌توانند تحت شرایط درست در زمان خطی مرتب کنند. این راهنمای جامع کران پایین مرتب‌سازی مبتنی‌بر‌مقایسه را با استدلال درخت تصمیم اثبات می‌کند، سپس سه الگوریتم زمان-خطی — counting sort، radix sort، و bucket sort — را همراه با فرضیات ورودی خاصی که هرکدام نیاز دارند توضیح می‌دهد.

ادامه

Quicksort: راهنمای کامل توصیف، کارایی، و تصادفی‌سازی

Quicksort یکی از پراستفاده‌ترین الگوریتم‌های مرتب‌سازی در عمل است، که به‌خاطر کارایی عالی حالت‌میانگین و عملیات درجا ارزشمند است، با وجود داشتن بدترین‌حالت نظری ضعیف. این راهنمای جامع الگوریتم مبتنی بر partition را با جزئیات پوشش می‌دهد، هم زمان اجرای بدترین‌حالت و هم مورد انتظار آن را تحلیل می‌کند، و توضیح می‌دهد تصادفی‌سازی چگونه آن را به یک الگوریتم به‌طور قابل‌اعتماد کارآمد صرف‌نظر از ترتیب ورودی تبدیل می‌کند.

ادامه

Heapsort و صف‌های اولویت: راهنمای کامل هیپ دودویی

هیپ دودویی یکی از ظریف‌ترین ساختارهای داده در علوم کامپیوتر است، که هم یک الگوریتم مرتب‌سازی کارآمد درجا و هم انتزاع صف اولویت مورد استفاده در سراسر طراحی الگوریتم را ممکن می‌سازد. این راهنمای جامع ویژگی‌های هیپ و نمایش آرایه‌ای، عملیات اصلی heapify، ساخت یک هیپ از یک آرایه مرتب‌نشده، الگوریتم کامل heapsort، و عملیات‌های صف اولویت ساخته‌شده روی هیپ‌ها را پوشش می‌دهد.

ادامه

<h2>Why Randomness Enters Algorithm Analysis</h2> <p>The worst-case, best-case, and average-case running times discussed earlier in this series all assume the algorithm itself behaves deterministically, and any variation comes purely from the input. A different situation arises when either the input distribution is unknown or an algorithm deliberately makes random choices during its own execution. Both situations require the tools of <code>Probabilistic Analysis</code>.</p> <h2>The Hiring Problem: A Motivating Example</h2> <p>Consider a company interviewing candidates one at a time for a position, always hiring the current best candidate seen so far and firing the previous hire. Each interview costs a small amount, but each hire costs significantly more, since it involves paperwork, onboarding, and severance for the person being replaced. The question is: what is the expected total hiring cost across the entire process?</p> <pre class="code-block"><code>HIRE-ASSISTANT(n): best = candidate 0 (a placeholder, ranked worst) for i = 1 to n: interview candidate i if candidate i is better than best: best = candidate i hire candidate i</code></pre><br> <p>If candidates arrive in the worst possible order — already sorted from worst to best — every single candidate is hired, resulting in <code>n</code> hires, a costly worst case. But if the order of candidates is random, far fewer hires are expected on average, since a random arrival order makes it unlikely that many consecutive candidates each set a new record.</p> <h2>Two Approaches to Handling the Order of Inputs</h2> <p>There are two distinct ways to reason about this randomness, and it is important not to confuse them.</p> <ul> <li><code>Probabilistic Analysis of a Deterministic Algorithm</code>: assume the input itself comes from some probability distribution (such as a uniformly random ordering of candidates), and analyze the expected running time of a fixed, non-random algorithm over that input distribution.</li> <li><code>Randomized Algorithms</code>: the algorithm itself makes random choices during execution (such as randomly shuffling the candidate order before processing them, regardless of the order they actually arrived in), guaranteeing good expected performance for any input, since the randomness comes from the algorithm rather than an assumption about the input.</li> </ul> <p>The second approach is generally more powerful and reliable in practice, since it removes any dependence on assumptions about how inputs are distributed in the real world, which may not hold. A <code>Randomized Algorithm</code> for the hiring problem simply permutes the candidates randomly before running the same procedure, guaranteeing the same good expected cost regardless of the input's original order.</p> <h2>Indicator Random Variables: A Powerful Analytical Tool</h2> <p>Computing an expected value directly can be complicated when many interacting events are involved. <code>Indicator Random Variables</code> provide an elegant technique that dramatically simplifies such calculations, especially when combined with the linearity of expectation.</p> <p>For an event <code>A</code>, define the indicator random variable:</p> <pre class="code-block"><code>I{A} = 1 if A occurs I{A} = 0 if A does not occur Key property: E[I{A}] = Pr{A}</code></pre><br> <p>The expected value of an indicator variable simply equals the probability of the event it indicates. This becomes powerful when combined with <code>Linearity of Expectation</code>, which states that the expected value of a sum of random variables equals the sum of their expected values, regardless of whether the variables are independent.</p> <pre class="code-block"><code>E[X1 + X2 + ... + Xn] = E[X1] + E[X2] + ... + E[Xn] This holds even when the Xi are NOT independent — a crucial and often surprising fact</code></pre><br> <h2>Applying Indicator Variables to the Hiring Problem</h2> <p>Let <code>Xi</code> be the indicator random variable for the event that candidate <code>i</code> is hired. The total number of hires is <code>X = X1 + X2 + ... + Xn</code>. By linearity of expectation:</p> <pre class="code-block"><code>E[X] = E[X1] + E[X2] + ... + E[Xn] = Σ Pr{candidate i is hired}</code></pre><br> <p>Candidate <code>i</code> is hired precisely when candidate <code>i</code> is the best among the first <code>i</code> candidates seen so far. If the candidates arrive in a uniformly random order, candidate <code>i</code> is equally likely to be the best, second-best, or any rank among the first <code>i</code> candidates, so:</p> <pre class="code-block"><code>Pr{candidate i is hired} = 1/i Therefore: E[X] = Σ (i=1 to n) 1/i = H(n) This is the Harmonic Series, and H(n) = Θ(ln n)</code></pre><br> <p>This remarkable result shows that, despite there being <code>n</code> candidates, the expected number of hires grows only logarithmically with <code>n</code>, a dramatic improvement over the worst-case scenario of <code>n</code> hires. This calculation, made simple through indicator variables, would be considerably more complex using direct probability calculations involving joint distributions.</p> <h2>Why This Technique Generalizes So Widely</h2> <p>The indicator random variable technique is not specific to the hiring problem; it is a general tool applicable whenever a quantity of interest can be expressed as a sum of simpler zero-or-one outcomes, even when those outcomes are correlated with each other. This makes it one of the most broadly useful techniques in the probabilistic analysis of algorithms, and it reappears throughout later topics in this series wherever expected running time needs to be computed.</p> <h2>Why Randomization Matters for Real-World Algorithm Design</h2> <p>Randomized algorithms are used throughout computer science specifically because they can guarantee good expected performance without needing any assumption about the distribution of real-world inputs, protecting against adversarial or unusually structured inputs that could otherwise trigger an algorithm's worst case. A prominent example, explored in depth later in this series, is randomized quicksort, where randomly shuffling the input before sorting protects against the specific input orderings that would otherwise trigger quicksort's quadratic worst case.</p>

برخی الگوریتم‌ها در حین اجرا انتخاب‌های تصادفی می‌کنند، و تحلیل رفتار مورد انتظارشان نیازمند جعبه‌ابزاری متفاوت از تحلیل بدترین‌حالت به‌تنهایی است. این راهنمای جامع تحلیل احتمالاتی را از طریق مسئله کلاسیک استخدام معرفی می‌کند، متغیرهای تصادفی نشانگر را به‌عنوان یک ابزار تحلیلی قدرتمند توضیح می‌دهد، و نشان می‌دهد تصادفی‌سازی چگونه می‌تواند کارایی مورد انتظار یک الگوریتم را بهبود بخشد.

ادامه

حل رابطه‌های بازگشتی: Substitution، Recursion-Tree، و روش استاد

زمان اجرای هر الگوریتم تقسیم‌و‌غلبه توسط یک رابطه بازگشتی توصیف می‌شود، و حل آن رابطه برای درک کارایی الگوریتم ضروری است. این راهنمای جامع سه تکنیک استاندارد برای حل رابطه‌های بازگشتی را پوشش می‌دهد: روش substitution برای اثبات یک کران حدس‌زده‌شده، روش recursion-tree برای تولید یک حدس، و روش استاد به‌عنوان یک میان‌بر سریع برای یک دسته رایج از رابطه‌های بازگشتی.

ادامه