رابطهٔ بازگشتی و قضیهٔ اصلی: از روی شکل رابطه، روش را انتخاب کن

جدول تصمیم: این شکل رابطه، این روش

اول شکل رابطه را ببین، بعد روش را انتخاب کن. همهٔ جواب‌های این جدول با محاسبهٔ عددی بررسی شده‌اند.

قضیهٔ اصلی در یک نگاه

قضیهٔ اصلی برای رابطه‌های «تقسیم و حل» است: مسئله به a زیرمسئله با اندازهٔ n/b شکسته می‌شود و شکستن و ترکیب f(n) هزینه دارد. کل کار این است که f(n) را با یک عدد مرجع مقایسه کنی:

عدد n^p هزینهٔ برگ‌های درخت بازگشت است و f(n) هزینهٔ ریشه. هر کدام بزرگ‌تر باشد، جواب را تعیین می‌کند. اگر هم‌اندازه باشند، همهٔ log n سطح درخت هزینهٔ یکسانی دارند و یک ضریب log اضافه می‌شود.

حالت ۲ را به شکل گسترش‌یافته نوشتیم، چون در تست‌ها زیاد پیش می‌آید: با k = 0 همان حالت آشنای Θ(n^p log n) است و با k = 1 مثلاً 2T(n/2) + n log n جوابش Θ(n log² n) می‌شود.

شرط نظم در حالت ۳ یعنی a·f(n/b) ≤ c·f(n) برای یک c < 1 و n های به‌اندازهٔ کافی بزرگ. به زبان ساده: هزینهٔ هر سطح درخت باید با یک ضریب ثابت از سطح بالایی‌اش کمتر باشد. برای f های چندجمله‌ای مثل n² یا n log n این شرط معمولاً خودبه‌خود برقرار است، ولی در تستی که صریحاً می‌پرسد «کدام حالت؟» باید چکش کنی.

پنج مثال حل‌شده

مثال ۱: 4T(n/2) + n²

a = 4 و b = 2، پس p = log₂ 4 = 2 و n^p = n². خود f(n) هم n² است؛ یعنی حالت ۲ با k = 0. جواب: Θ(n² log n).

مثال ۲: 7T(n/2) + n²

این رابطهٔ ضرب ماتریس استراسن است. p = log₂ 7 ≈ 2٫81 و f(n) = n² به‌طور چندجمله‌ای کوچک‌تر از n^2٫81 است؛ حالت ۱. جواب: Θ(n^(log₂ 7)) ≈ Θ(n^2٫81). اگر به‌جای ۷ زیرمسئله ۸ تا بود، یعنی ضرب ماتریس معمولی، جواب Θ(n³) می‌شد. همین یک زیرمسئلهٔ کمتر است که استراسن را سریع‌تر می‌کند.

مثال ۳: 3T(n/4) + n log n

p = log₄ 3 ≈ 0٫79. f(n) = n log n از n^0٫79 به‌طور چندجمله‌ای بزرگ‌تر است؛ مثلاً با ε = 0٫2 هم بزرگ‌تر می‌ماند. شرط نظم: 3·(n/4)·log(n/4) ≤ (3/4)·n log n، پس c = 3/4 کار می‌کند. حالت ۳؛ جواب: Θ(n log n).

مثال ۴: T(n/3) + T(2n/3) + n

دو زیرمسئله با اندازه‌های متفاوت داریم، پس قضیهٔ اصلی مستقیم به کار نمی‌آید. درخت بازگشت را بکش: جمع اندازه‌های هر سطح n/3 + 2n/3 = n است، پس هر سطح کامل حداکثر n هزینه دارد. کوتاه‌ترین شاخه حدود log₃ n سطح دارد و بلندترین حدود log₃/₂ n سطح. هر دو از مرتبهٔ log n هستند. جواب: Θ(n log n).

قاعدهٔ کلی این شکل: اگر جمع ضریب‌ها برابر ۱ باشد (α + β = 1)، جواب Θ(n log n) است. اگر کمتر از ۱ باشد، مثل T(n/2) + T(n/4) + n، هزینهٔ سطح‌ها یک سری هندسی نزولی می‌سازد و جواب Θ(n) است.

مثال ۵: 2T(√n) + log n

رادیکال یعنی تغییر متغیر. بگذار m = log n، پس √n یعنی m/2. اگر S(m) = T(2ᵐ) بگیری، رابطه می‌شود S(m) = 2S(m/2) + m. این همان رابطهٔ مرتب‌سازی ادغامی است و جوابش Θ(m log m) است. حالا m را برگردان: Θ(log n · log log n).

سه اشتباه رایج

اشتباه ۱: 2T(n/2) + n/log n

اینجا p = 1 و n^p = n. f(n) = n/log n از n کوچک‌تر است، ولی به‌طور چندجمله‌ای کوچک‌تر نیست؛ هیچ ε > 0 وجود ندارد که n/log n = O(n^(1−ε)) شود. پس حالت ۱ برقرار نیست. حالت ۲ گسترش‌یافته هم فقط k ≥ 0 را پوشش می‌دهد و اینجا k = −1 است. قضیهٔ اصلی در شکل پایه‌اش جوابی نمی‌دهد.

با درخت بازگشت حلش کن: سطح i ام 2ⁱ زیرمسئله دارد، هر کدام با هزینهٔ (n/2ⁱ)/log(n/2ⁱ)، پس هزینهٔ کل سطح n/(log n − i) است. جمع این‌ها از i = 0 تا log n − 1 برابر n ضرب در سری هارمونیک تا log n است. جواب: Θ(n log log n).

اشتباه ۲: T(n−1) را با قضیهٔ اصلی حل کردن

قضیهٔ اصلی برای وقتی است که n بر عددی تقسیم می‌شود، نه وقتی که از آن کم می‌شود. 2T(n−1) + 1 شبیه 2T(n/2) + 1 به نظر می‌رسد، ولی جوابش Θ(2ⁿ) است، نه Θ(n). اگر رابطه را باز کنی، 1 + 2 + 4 + … + 2ⁿ⁻¹ می‌بینی.

اشتباه ۳: n log n را «چندجمله‌ای بزرگ‌تر» از n فرض کردن

در 2T(n/2) + n log n وسوسه می‌شوی بگویی f از n بزرگ‌تر است، پس حالت ۳ و جواب Θ(n log n). ولی n log n به‌طور چندجمله‌ای از n بزرگ‌تر نیست؛ log n از هر n^ε کندتر رشد می‌کند. این حالت ۲ گسترش‌یافته با k = 1 است و جواب درست Θ(n log² n) است. اگر حالت ۳ را بزنی، دقیقاً یک ضریب log کم آورده‌ای.

پرسش‌های پرتکرار

قضیهٔ اصلی کی جواب نمی‌دهد؟

وقتی رابطه به شکل aT(n/b) + f(n) نیست، مثل T(n−1)، دو زیرمسئلهٔ نامساوی یا رادیکال. همچنین وقتی f(n) در «فاصلهٔ بین حالت‌ها» می‌افتد، مثل n/log n در برابر n، یا وقتی در حالت ۳ شرط نظم برقرار نیست. در این موارد سراغ درخت بازگشت، باز کردن یا تغییر متغیر برو.

آیا کف و سقف، مثل ⌊n/2⌋، جواب را عوض می‌کند؟

برای مرتبهٔ رشد در رابطه‌های معمول کنکوری، نه. 2T(⌊n/2⌋) + n و 2T(⌈n/2⌉) + n هر دو Θ(n log n) هستند. می‌توانی n را توانی از b بگیری و کف و سقف را نادیده بگیری.

برای T(n−1) + f(n) از چه روشی استفاده کنم؟

رابطه را باز کن: T(n) = f(n) + f(n−1) + … + f(1)، پس جواب همان مجموع f است. مثلاً T(n−1) + n می‌شود Θ(n²) و T(n−1) + n² می‌شود Θ(n³). اگر ضریب T(n−1) بزرگ‌تر از ۱ باشد، رشد نمایی است.

قاعدهٔ α + β برای T(αn) + T(βn) + n چیست؟

اگر α + β = 1 باشد جواب Θ(n log n) است و اگر α + β < 1 باشد جواب Θ(n). در حالت دوم هزینهٔ هر سطح درخت کسری ثابت از سطح قبلی است و سری هندسی نزولی می‌شود.

این مبحث در کلاس

من ارشدم را در دانشگاه صنعتی شریف، در نرم‌افزار با گرایش الگوریتم و محاسبات گرفتم. تحلیل رابطه‌های بازگشتی، از قضیهٔ اصلی تا درخت بازگشت و تغییر متغیر، بخشی از دورهٔ داده‌ساختار و الگوریتم من است؛ با ویدیو، جزوهٔ کامل و تست‌های حل‌شده. از ۱۲ تست داده‌ساختار و الگوریتم کنکور ۱۴۰۵، نُه‌تا پیش‌تر در کلاس کار شده بود؛ سند این مقایسه در صفحهٔ مستندات هست. دوره‌ها به‌زودی روی همین سایت منتشر می‌شوند و ویدیوی رایگان چند جلسه از کلاس‌هایم هم به‌زودی در صفحهٔ ویدیوهای رایگان همین سایت قرار می‌گیرد.

قدم بعدی تو

این شش رابطه را بدون نگاه کردن به جواب‌ها حل کن و فقط روش را در ده ثانیه انتخاب کن: 3T(n/3) + n، T(n−1) + log n، 9T(n/3) + n، T(√n) + log n، T(n/4) + T(3n/4) + n و 4T(n/2) + n³. بعد جواب‌ها را با جدول تصمیم و قضیهٔ اصلی بسنج. اگر روش را درست انتخاب کنی، بقیه‌اش چند خط حساب است.

جواب‌ها به همان ترتیب: Θ(n log n)، Θ(n log n)، Θ(n²)، Θ(log n)، Θ(n log n) و Θ(n³).