راهنمای انتخاب الگوریتم
جدول جامع تصمیم‌گیری: از ویژگی‌های مسئله به الگوریتم درست — مرجع نهایی انتخاب الگو
نقشه نهایی
جمع‌بندی کل دوره در یک جدول تصمیم‌گیری — از «چه مسئله‌ای دارم» به «کدام الگو»:
جدول تشخیص الگو
| ویژگی مسئله | الگو | پیچیدگی معمول |
|---|---|---|
| آرایه مرتب + جفت/سه‌تایی | دو اشاره‌گر | O(n) / O(n²) |
| زیرآرایه/زیررشته پیوسته بهینه | پنجره لغزان | O(n) |
| لیست پیوندی: حلقه/وسط | کند و تند | O(n), O(1) |
| فواصل زمانی: ادغام/تقاطع | مرتب‌سازی + اسکن | O(n log n) |
| کمینه بیشینه با شرط | دودویی روی پاسخ | O(n log range) |
| همه ترکیب‌ها/جایگشت‌ها | Backtracking | نمایی + هرس |
| بهینه + همپوشانی زیرمسئله | DP | O(حالت×انتقال) |
| جستجوی الگو در متن | KMP / Rabin-Karp | O(n+m) |
| پالیندروم‌ها | توسعه از مرکز | O(n²) |
| دو رشته مشترک | LCS (DP) | O(mn) |
| اعداد: جفت/تکی | XOR | O(n) |
| توان/باقیمانده بزرگ | توان سریع | O(log n) |
| گراف + وابستگی/ترتیب | توپولوژیک (Kahn) | O(V+E) |
| گراف دو گروه | رنگ‌آمیزی BFS | O(V+E) |
| انتخاب محلی اثبات‌شده | حریصانه | O(n log n) |
چک‌لیست قبل از کدنویسی
- ورودی مرتب است؟ (دو اشاره‌گر/دودویی)
- «پیوسته» می‌خواهم یا آزاد؟ (پنجره vs DP)
- «همه راه‌ها» یا «بهترین»؟ (Backtracking vs DP/حریصانه)
- حجم داده چقدر است؟ (n=10⁶ یعنی O(n) یا O(n log n) لازم)
- حافظه محدود است؟ (کند/تند به جای هش)
قانون سرانگشتی حجم داده
| n | پیچیدگی قابل قبول |
|---|---|
| ≤ ۱۲ | O(n!) — جایگشت‌ها |
| ≤ ۲۵ | O(2ⁿ) — Backtracking |
| ≤ ۱۰۰ | O(n³) |
| ≤ ۱۰⁴ | O(n²) |
| ≤ ۱۰⁶ | O(n log n) |
| ≤ ۱۰⁹ | O(n) یا O(log n) |
نکته نهایی: این جدول را «حفظ نکنید» — با حل مسئله، خودش در ذهن شما می‌نشیند. بعد از هر مسئله: «کدام الگو بود؟ چه چیزی لوش داد؟» — این بازتاب، استادتان می‌کند.
جمع‌بندی
- ۱۵ الگو = پوشش اکثر مسائل
- چک‌لیست ۵ سؤالی قبل از کد
- حجم داده، سقف پیچیدگی را دیکته می‌کند
- بازتاب بعد از هر مسئله = تسلط
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.