چرا الگوریتمهای تقسیموغلبه به رابطههای بازگشتی نیاز دارند
یک الگوریتم تقسیموغلبه، همانطور که پیشتر در این مجموعه درباره ضرب ماتریس معرفی شد، یک مسئله به اندازه n را به زیرمسئلههای کوچکتر میشکند، هرکدام را بهطور بازگشتی حل میکند، و نتایج را ترکیب میکند. این ساختار بهطور طبیعی یک Recurrence (رابطه بازگشتی) تولید میکند: یک معادله یا نامعادله که یک تابع را برحسب مقدارش روی ورودیهای کوچکتر توصیف میکند. حل یک رابطه بازگشتی یعنی یافتن یک کران مجانبی صریح و بسته، که معمولاً با نمادگذاریای که پیشتر در این مجموعه پوشش داده شد بیان میشود.
یک رابطه بازگشتی تقسیموغلبه کلی این شکل را دارد:
T(n) = a · T(n/b) + f(n)جایی که a تعداد زیرمسئلههای ایجادشده است، n/b اندازه هر زیرمسئله است، و f(n) زمان صرفشده برای تقسیم مسئله و ترکیب راهحلهای زیرمسئله است.
روش Substitution: حدس بزن و اثبات کن
Substitution Method شامل حدس زدن شکل راهحل، سپس استفاده از استقرای ریاضی برای اثبات درستی حدس است. این روش به هیچ فرمول خاصی نیاز ندارد، اما به یک حدس اولیه خوب نیاز دارد، که اغلب توسط تجربه یا یک تحلیل recursion-tree اطلاعرسانی میشود.
بهعنوان یک مثال کارشده، اثبات اینکه T(n) = 2T(n/2) + n برابر O(n log n) است را در نظر بگیرید. حدس این است که T(n) ≤ cn log n برای یک ثابت c و n بهاندازه کافی بزرگ.
فرض استقرایی: فرض کن T(n/2) ≤ c(n/2)log(n/2)
جایگذاری در رابطه بازگشتی:
T(n) = 2T(n/2) + n
≤ 2c(n/2)log(n/2) + n
= cn log(n/2) + n
= cn(log n - 1) + n
= cn log n - cn + n
≤ cn log n
گام آخر هروقت c ≥ 1 برقرار است،
چون آنگاه -cn + n ≤ 0این گام استقرایی را تأیید میکند؛ یک استدلال حالتپایه جداگانه برای n کوچک اثبات را کامل میکند، و ثابت میکند T(n) = O(n log n).
یک دام رایج هنگام استفاده از substitution، اثبات یک کران ضعیفتر از نیاز با استفاده از یک فرض استقرایی بهاندازه کافی دقیق نیست. گاهی تکنیکی به نام Subtracting a Lower-Order Term (کم کردن یک جمله مرتبهپایینتر) ضروری است: بهجای حدس زدن T(n) ≤ cn، حدس زدن T(n) ≤ cn - b برای یک ثابت b میتواند استقرا را وقتی حدس سادهتر شکست میخورد، پیش ببرد.
روش Recursion-Tree: تصویرسازی کل کار
Recursion-Tree Method راهی سیستماتیک برای تولید یک حدس خوب برای روش substitution با تصویرسازی رابطه بازگشتی بهصورت یک درخت فراهم میکند، جایی که هر گره هزینه یک زیرمسئله در یک سطح بازگشت را نشان میدهد.
رابطه بازگشتی T(n) = 3T(n/4) + Θ(n²) را در نظر بگیرید. درخت بازگشت اینطور بهنظر میرسد:
سطح 0: n² — هزینه: n²
سطح 1: (n/4)² (n/4)² (n/4)² — هزینه: 3(n/4)²
سطح 2: 9 گره، هرکدام (n/16)² — هزینه: 9(n/16)²
...ادامه تا زیرمسئلهها به اندازه 1 برسند...
سطح i دارای 3^i گره است، هرکدام به اندازه n/4^i،
پس هزینه در سطح i برابر 3^i · (n/4^i)² است
= n² · (3/16)^iجمع هزینه در سراسر همه سطوح، از سطح ۰ تا برگها، یک سری هندسی میدهد:
T(n) = n² · Σ (i=0 تا log₄n) (3/16)^i
از آنجا که 3/16 < 1، این سری هندسی به
یک ثابت همگرا میشود با رشد تعداد جملات، محدودشده توسط:
1 / (1 - 3/16) = 16/13
بنابراین T(n) = O(n²)درخت بازگشت آشکار میکند هزینه توسط سطح ریشه غالب است، چون نسبت بین سطوح بهطور هندسی کوچک میشود. این بینش — که سطح بالا غالب است — تبدیل به حدسی میشود که باید با استفاده از روش substitution توصیفشده در بالا بهطور دقیق تأیید شود.
روش استاد: یک فرمول مستقیم برای موارد رایج
Master Method یک راهحل سریع و "کتابآشپزی" برای رابطههای بازگشتی فرم استاندارد تقسیموغلبه T(n) = aT(n/b) + f(n) فراهم میکند، جایی که a ≥ 1 و b > 1 ثابتاند و f(n) از نظر مجانبی مثبت است. با مقایسه f(n) در برابر n^(log_b a)، هزینهای که خود بازگشت (نادیدهگرفتن گام ترکیب) تولید میکند، کار میکند.
قضیه استاد — سه حالت:
حالت ۱: اگر f(n) = O(n^(log_b a - ε)) برای یک ε > 0،
آنگاه T(n) = Θ(n^(log_b a))
(زیرمسئلههای بازگشتی غالباند)
حالت ۲: اگر f(n) = Θ(n^(log_b a))،
آنگاه T(n) = Θ(n^(log_b a) · log n)
(هزینه بازگشت و ترکیب متوازناند)
حالت ۳: اگر f(n) = Ω(n^(log_b a + ε)) برای یک ε > 0،
و شرط قاعدهمندی a·f(n/b) ≤ c·f(n)
برای یک c < 1 و n بزرگ برقرار باشد،
آنگاه T(n) = Θ(f(n))
(گام ترکیب غالب است)بهکارگیری این روی رابطههای بازگشتی ضرب ماتریس پیشتر در این مجموعه، روش را ملموس میکند.
تقسیموغلبه ساده: T(n) = 8T(n/2) + Θ(n²)
a = 8, b = 2, پس n^(log_b a) = n^(log₂8) = n³
f(n) = n² = O(n^(3-ε)) برای ε = 1 → حالت ۱
T(n) = Θ(n³)
الگوریتم اشتراسن: T(n) = 7T(n/2) + Θ(n²)
a = 7, b = 2, پس n^(log_b a) = n^(log₂7) ≈ n^2.807
f(n) = n² = O(n^(2.807-ε)) → حالت ۱
T(n) = Θ(n^log₂7) ≈ Θ(n^2.807)یک مثال رایج دیگر T(n) = 2T(n/2) + n است، که الگوریتمهایی مانند merge sort را توصیف میکند.
a = 2, b = 2, پس n^(log_b a) = n^(log₂2) = n¹ = n
f(n) = n = Θ(n^1) → حالت ۲ دقیقاً اعمال میشود
T(n) = Θ(n log n)چرا روش استاد محدودیت دارد
روش استاد هر رابطه بازگشتی ممکن را پوشش نمیدهد. یک شکاف بین حالت ۱ و حالت ۲ وجود دارد، و شکاف دیگری بین حالت ۲ و حالت ۳، جایی که f(n) از نظر مجانبی بزرگتر یا کوچکتر از تابع مقایسه است اما نه با یک فاکتور چندجملهای. در این موارد شکاف، و هروقت شرط قاعدهمندی در حالت ۳ شکست بخورد، روش استاد صرفاً اعمال نمیشود، و باید بهجای آن از روشهای substitution یا recursion-tree توصیفشده در بالا استفاده شود.
علاوهبراین، روش استاد فقط رابطههای بازگشتی از این فرم مشخص تقسیموغلبه با زیرمسئلههایی به اندازه یکسان را مدیریت میکند. رابطههای بازگشتی با اندازه زیرمسئله نابرابر، مانند آنهایی که از برخی الگوریتمهای تصادفی که بعداً در این مجموعه بحث میشوند ناشی میشوند، به تکنیکهای عمومیتری مانند روش Akra-Bazzi نیاز دارند، گسترشی که در بخشهای پیشرفتهتر نظریه رابطه بازگشتی پوشش داده میشود.
انتخاب ابزار درست
در عمل، روش استاد باید ابتدا برای هر رابطه بازگشتی استاندارد تقسیموغلبه امتحان شود، چون تا حد زیادی سریعترین تکنیک هنگام قابلاعمالبودن است. وقتی شرایط روش استاد برآورده نمیشوند، روش recursion-tree راهی سیستماتیک برای تولید یک حدس آگاهانه درباره شکل راهحل فراهم میکند، و روش substitution سپس اثبات دقیق درست بودن حدس را فراهم میکند. با هم، این سه تکنیک اکثریت قریببهاتفاق رابطههای بازگشتی مواجهشده هنگام تحلیل الگوریتمهای تقسیموغلبه را پوشش میدهند.