الگوریتم چیست و چگونه تحلیل می‌شود: راهنمای کامل شروع

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

الگوریتم دقیقاً چیست

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

Finiteness (محدودیت): الگوریتم باید پس از تعداد محدودی گام خاتمه یابد، صرف‌نظر از اینکه چه ورودی معتبری دریافت کند.
Definiteness (قطعیت): هر گام باید دقیق و بدون ابهام مشخص شده باشد، بدون هیچ جایی برای تفسیر.
Input and Output (ورودی و خروجی): الگوریتم صفر یا چند ورودی می‌گیرد و حداقل یک خروجی مرتبط با آن ورودی‌ها تولید می‌کند.
Effectiveness (اثربخشی): هر گام باید به‌اندازه کافی پایه باشد که، از نظر اصولی، بتوان آن را با یک فرد با استفاده از کاغذ و مداد در زمانی محدود انجام داد.

یک Problem (مسئله) یک پرسش کلی برای پاسخ‌دادن است، معمولاً با پارامترهای مشخص‌نشده، مانند "این مجموعه از اعداد را مرتب کن." یک مجموعه مشخص از مقادیر پارامتر، مانند یک لیست مرتب‌نشده خاص، Problem Instance (نمونه مسئله) نامیده می‌شود. یک الگوریتم Correct (درست) است اگر برای هر نمونه مسئله ممکن، خروجی صحیح را تولید کند، و گفته می‌شود آن مسئله محاسباتی را Solve (حل) می‌کند.

چرا مطالعه الگوریتم‌ها همچنان اهمیت دارد

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

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

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

یک مثال کامل اول: Insertion Sort

برای زمینی کردن این ایده‌های انتزاعی، Sorting Problem (مسئله مرتب‌سازی) را در نظر بگیرید: با داشتن یک توالی از اعداد، آن‌ها را به ترتیب نزولی-نداشته مرتب کن. یکی از ساده‌ترین الگوریتم‌ها برای حل این مسئله Insertion Sort است، که به شیوه‌ای کار می‌کند که بسیاری از افراد به‌طور طبیعی یک دست از کارت‌های بازی را مرتب می‌کنند.

Insertion Sort چگونه کار می‌کند

Insertion sort ورودی را یکی‌یکی پردازش می‌کند. در هر گام، عنصر بعدی مرتب‌نشده را می‌گیرد و آن را در موقعیت درست خودش در میان عناصر از‌قبل-مرتب‌شده‌ای که قبل از آن قرار دارند وارد می‌کند.

INSERTION-SORT(A, n):
  for i = 2 to n:
      key = A[i]
      j = i - 1
      while j > 0 and A[j] > key:
          A[j + 1] = A[j]
          j = j - 1
      A[j + 1] = key

ردیابی یک مثال کوچک این را ملموس می‌کند. فرض کنید آرایه به‌صورت [5, 2, 4, 6, 1, 3] شروع می‌شود.

شروع:         [5, 2, 4, 6, 1, 3]
پس از i=2:    [2, 5, 4, 6, 1, 3]
پس از i=3:    [2, 4, 5, 6, 1, 3]
پس از i=4:    [2, 4, 5, 6, 1, 3]
پس از i=5:    [1, 2, 4, 5, 6, 3]
پس از i=6:    [1, 2, 3, 4, 5, 6]

در هر تکرار، عنصر "key" با بخش مرتب‌شده در سمت چپش مقایسه می‌شود و به عقب جابه‌جا می‌شود تا در موقعیت درست قرار گیرد، و ناحیه مرتب‌شده را در هر گام یک عنصر بزرگ‌تر می‌کند.

اثبات درستی با یک Loop Invariant

برای استدلال دقیق اینکه insertion sort همیشه یک آرایه به‌درستی‌مرتب‌شده تولید می‌کند، دانشمندان کامپیوتر از تکنیکی به نام Loop Invariant (پایاننده حلقه) استفاده می‌کنند: ویژگی‌ای که پیش از شروع حلقه درست است، پیش از هر تکرار درست باقی می‌ماند، و همراه با شرط پایان حلقه، درستی الگوریتم را وقتی حلقه پایان می‌یابد نتیجه می‌دهد. این شبیه استقرای ریاضی است.

برای insertion sort، loop invariant این است: در شروع هر تکرار حلقه بیرونی، زیرآرایه A[1..i-1] شامل عناصر اصلی‌ای است که در ابتدا در آن زیرآرایه بودند، اما اکنون به‌صورت مرتب‌شده.

Initialization (مقداردهی اولیه): پیش از اولین تکرار، وقتی i = 2، زیرآرایه A[1..1] فقط یک عنصر تکی دارد، که به‌طور بدیهی مرتب است.
Maintenance (نگهداری): هر تکرار حلقه، پایاننده را در شروعش درست فرض می‌کند و نشان می‌دهد پس از آن همچنان درست باقی می‌ماند، با درج درست A[i] در موقعیت مرتب‌شده مناسبش درون زیرآرایه مرتب‌شده در حال رشد.
Termination (پایان): وقتی حلقه پایان می‌یابد، i برابر با n + 1 شده است، پس پایاننده بیان می‌کند زیرآرایه A[1..n]، کل آرایه، مرتب است — که دقیقاً همان چیزی است که باید اثبات می‌شد.

تحلیل اینکه یک الگوریتم چقدر طول می‌کشد

فراتر از درستی، Running Time (زمان اجرا) یک الگوریتم یک نگرانی مرکزی است. زمان اجرا معمولاً به‌عنوان تابعی از Input Size (اندازه ورودی)، تعداد عناصری که پردازش می‌شوند، سنجیده می‌شود، و به‌صورت تعداد عملیات‌های پایه یا "گام‌هایی" که الگوریتم انجام می‌دهد بیان می‌شود.

تحلیل بدترین‌حالت، بهترین‌حالت، و حالت‌میانگین

از آنجا که زمان اجرا می‌تواند بسته به ورودی خاص متفاوت باشد، نه فقط اندازه‌اش، سه مفهوم متمایز از زمان اجرا معمولاً استفاده می‌شوند.

Worst-Case Running Time (زمان اجرای بدترین‌حالت): حداکثر زمان اجرا در سراسر همه ورودی‌های یک اندازه مشخص. این متداول‌ترین سنجه است، چون یک سقف تضمین‌شده صرف‌نظر از ورودی فراهم می‌کند.
Best-Case Running Time (زمان اجرای بهترین‌حالت): حداقل زمان اجرا در سراسر همه ورودی‌های یک اندازه مشخص. این به‌ندرت به‌تنهایی مفید است، چون هیچ تضمینی درباره کارایی معمول نمی‌دهد.
Average-Case Running Time (زمان اجرای حالت‌میانگین): زمان اجرای مورد انتظار روی یک توزیع فرض‌شده از ورودی‌ها. این می‌تواند مفید باشد اما به‌شدت به واقع‌بینانه بودن توزیع فرض‌شده بستگی دارد.

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

چرا تحلیل بدترین‌حالت انتخاب استاندارد است

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

طراحی الگوریتم‌ها: تدریجی در مقابل تقسیم‌و‌غلبه

Insertion sort از یک رویکرد طراحی Incremental (تدریجی) پیروی می‌کند: راه‌حل را به‌تدریج، یک عنصر در یک زمان، می‌سازد، و یک راه‌حل جزئی را تا حل کل مسئله گسترش می‌دهد. این رویکرد تمایل دارد الگوریتم‌های ساده و قابل‌فهم تولید کند، هرچند نه همیشه کارآمدترین‌ها برای ورودی‌های بزرگ.

یک الگوی طراحی جایگزین و اغلب قدرتمندتر، که در موضوع اصلی بعدی بررسی می‌شود، Divide-and-Conquer (تقسیم‌و‌غلبه) است، که یک مسئله را به زیرمسئله‌های کوچک‌تری از همان نوع می‌شکند، هرکدام را به‌طور مستقل (اغلب بازگشتی) حل می‌کند، و سپس راه‌حل‌هایشان را ترکیب می‌کند. این رویکرد اغلب الگوریتم‌های کارآمدتری برای مسائل در مقیاس بزرگ تولید می‌کند، به قیمت پیچیدگی مفهومی تا حدی بیشتر.

چرا این پایه اهمیت دارد

هر الگوریتمی که در باقی این مجموعه مطالعه می‌شود مستقیماً روی مفاهیم معرفی‌شده در اینجا بنا می‌شود: تعاریف دقیق مسئله، استدلال‌های درستی سخت‌گیرانه با استفاده از تکنیک‌هایی مانند loop invariant، و تحلیل دقیق زمان اجرا با استفاده از استدلال بدترین‌حالت. تسلط بر این ابزارهای پایه پیش از حرکت به الگوریتم‌های پیشرفته‌تر، امکان می‌دهد هر الگوریتم جدیدی که مواجه می‌شود با همان دقتی که در این مقاله برای insertion 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 برای تولید یک حدس، و روش استاد به‌عنوان یک میان‌بر سریع برای یک دسته رایج از رابطه‌های بازگشتی.

ادامه

تقسیم‌و‌غلبه برای ضرب ماتریس: از رویکرد ساده تا الگوریتم اشتراسن

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

ادامه

نمادگذاری مجانبی: راهنمای کامل O، Ω، و Θ

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

ادامه