تحلیل الگوریتم و Big O
تحلیل پیشرفته الگوریتم: بهترین/بدترین/میانگین، پیچیدگی مکانی، Amortized و تحلیل بازگشتی با رابطه بازگشتی
فراتر از Big O پایه
در دوره DSA، Big O مقدماتی را دیدید. اینجا عمیق‌تر می‌شویم: تحلیل همه حالات، پیچیدگی مکانی و تحلیل الگوریتم‌های بازگشتی.
سه دیدگاه زمانی
| دیدگاه | معنا | مثال (جستجوی خطی) |
|---|---|---|
| بهترین (Best) | خوش‌شانسی‌ترین ورودی | هدف = عنصر اول: O(1) |
| بدترین (Worst) | بدشانسی‌ترین ورودی | هدف آخر/موجود نیست: O(n) |
| میانگین (Average) | انتظار روی ورودی تصادفی | O(n/2) = O(n) |
معیار استاندارد بدترین حالت است (تضمین می‌دهد) اما در الگوریتم‌های تصادفی، میانگین هم مهم می‌شود.
پیچیدگی مکانی
حافظه هم مثل زمان تحلیل می‌شود:
- آرایه کمکی n تایی ← O(n) فضای اضافی
- بازگشت با عمق d ← O(d) پشته فراخوانی!
- مرتب‌سازی درجا (Heap) ← O(1) در برابر Merge با O(n)
Amortized — هزینه میانگین‌گیری‌شده
append در list پایتون: معمولاً O(1) اما گاهی (وقتی ظرفیت پر شود) O(n) برای کپی! هزینه Amortized = O(1) چون کپی‌های نادر، روی کل عملیات پخش می‌شوند. مثل هزینه سالانه بیمه: یک جریمه بزرگ، میانگین‌گیری روی همه سال.
تحلیل بازگشت با رابطه بازگشتی
برای الگوریتم‌های بازگشتی، رابطه بازگشتی بنویسید:
T(n) = a × T(n/b) + f(n)
↑ ↑ ↑
شاخه‌ها اندازه زیر کار این سطحمثالها:
| الگوریتم | رابطه | نتیجه |
|---|---|---|
| جستجوی دودویی | T(n) = T(n/2) + O(1) | O(log n) |
| Merge Sort | T(n) = 2T(n/2) + O(n) | O(n log n) |
| فیبوناچی ساده | T(n) = T(n−1) + T(n−2) | O(2ⁿ)! |
قضیه اصلی (Master Theorem) — شهود
بدون حفظ فرمول، سه حالت دارید:
- کار هر سطح سریع‌تر از کاهش زیرمسئله رشد می‌کند ← ریشه‌ها غالب (مثل دودویی: O(log n))
- هر دو برابر ← O(n log n) (مثل Merge)
- کار هر سطح سنگین‌تر ← کار ریشه غالب (مثل فیبوناچی ساده)
نکته عملی: در مصاحبه، وقتی راه‌حل دادید حتماً Big O زمان «و فضا» را بگویید — فراموش‌کردن فضا، اشتباه رایج داوطلبان است!
جمع‌بندی
- سه دیدگاه: بهترین/بدترین/میانگین — بدترین معیار است
- فضا: آرایه کمکی + عمق پشته بازگشت
- Amortized: هزینه نادر بزرگ، میانگین کوچک
- بازگشت: رابطه T(n) بنویسید و با قضیه اصلی حل کنید
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.