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

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

یک 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 اعمال شد، ارزیابی شود.