تقسیم و حل (Divide and Conquer)
تکنیک تقسیم و حل: شکستن مسئله به زیرمسئله‌های مستقل، حل بازگشتی و ترکیب؛ پایه Merge و Quick Sort
تقسیم و حل چیست؟
Divide and Conquer سه مرحله دارد:
- تقسیم (Divide): مسئله را به چند زیرمسئله مستقل کوچک‌تر بشکن
- حل (Conquer): زیرمسئله‌ها را بازگشتی حل کن (اگر خیلی کوچک‌اند، مستقیم)
- ترکیب (Combine): جواب‌ها را به جواب اصلی ترکیب کن
مثال‌های آشنا
| الگوریتم | تقسیم | حل | ترکیب |
|---|---|---|---|
| Merge Sort | نصف کردن آرایه | مرتب‌کردن بازگشتی | ادغام دو نصف مرتب |
| Quick Sort | پارتیشن حول پیوت | مرتب‌کردن دو بخش | نیازی نیست! (درجا) |
| جستجوی دودویی | انتخاب نیمه درست | جستجو در همان نیمه | مستقیم پاسخ |
| ضرب اعداد بزرگ | شکستن ارقام | ضرب‌های کوچک‌تر | جمع جابه‌جایی‌ها |
چرا کارآمد است؟
تقسیم لگاریتمی است: هر تقسیم اندازه را نصف می‌کند، پس فقط log n سطح داریم. اگر هر سطح O(n) کار کند، کل: O(n log n) — انقلاب نسبت به O(n²)!
مثال غیر از مرتب‌سازی: Maximum Subarray
پیدا کردن زیرآرایه متوالی با بیشترین مجموع:
- آرایه را نصف کن
- بهترین زیرآرایه: یا کاملاً در چپ، یا کاملاً در راست، یا از وسط عبور می‌کند
- حالت عبوری: از وسط به دو طرف بیشترین امتداد را بگیر
- بیشینه‌ی سه حالت
تقسیم و حل در برابر برنامه‌نویسی پویا
| ویژگی | تقسیم و حل | برنامه‌نویسی پویا |
|---|---|---|
| زیرمسئله‌ها | مستقل ✓ | همپوشان! |
| محاسبه تکراری | ندارد | دارد ← ذخیره (memo) |
| مثال | Merge Sort، جستجوی دودویی | فیبوناچی، کوله‌پشتی |
نکته: اگر زیرمسئله‌ها مستقل‌اند ← تقسیم و حل. اگر تکراری/همپوشان‌اند ← برنامه‌نویسی پویا (مبحث بعدی). تشخیص این تفاوت، کلید طراحی الگوریتم است!
جمع‌بندی
- سه‌مرحله‌ای: تقسیم ← حل بازگشتی ← ترکیب
- تقسیم لگاریتمی = کارایی O(n log n)
- پایه Merge/Quick Sort و جستجوی دودویی
- برای زیرمسئله‌های مستقل؛ همپوشان ← DP
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.