قضیه اصلی واکاوی الگوریتم‌ها

قضیه اصلی واکاوی (تحلیل) الگوریتم‌ها که حالتی خاص از قضیهٔ اکرا-بازی است در تحلیل الگوریتم‌ها، یک راه حل سرراست برای حالت‌های مجانبی که در عمل در انواع روابط بازگشتی رخ می‌دهند، ارائه می‌کند. این قضیه با کتاب درسی معروف مقدمه‌ای بر الگوریتم‌ها نوشتهٔ کرمن، لیسرسن، ریوست و استین به شهرت رسید. این قضیه در بخش ۴٫۳ دراین کتاب معرفی شده‌است و متعاقباً در بخش ۴٫۴ به اثبات رسیده‌است. هرچند که نمی‌توان تمامی روابط بازگشتی را به کمک قضیهٔ اصلی حل کرد.

شکل کلی

قضیهٔ اصلی روابطی را مورد بررسی قرار می‌دهد که به شکل زیر باشند:

$T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n) \;\;\;\; \mbox{where} \;\; a \geq 1 \mbox{, } b > 1.$

در استفاده از رابطهٔ فوق برای یک الگوریتم بازگشتی معنای علائم به کار رفته، به شرح زیر است: *n اندازهٔ مسأله‌است.

• a تعداد زیرمسأله هاست.
• n/b اندازهٔ هر یک از زیرمسأله هاست. (در اینجا فرض شده‌است که اندازهٔ همهٔ زیرمسأله‌ها با هم برابر است.)
• (f(n هزینهٔ بخش غیر بازگشتی است که شامل هزینهٔ تقسیم مسأله به زیرمسأله‌ها و هزینهٔ ادغام پاسخ به زیرمسأله هاست.

در سه حالت می‌توان یک حد مجانبی مشخص کرد:

حالت ۱

شکل کلی

اگر ثابت $\epsilon > 0$ وجود داشته باشد به طوری که رابطهٔ $f(n) = \mathcal{O}\left(n^{\log_b \left(a \right) - \epsilon} \right)$ برقرار باشد،

آن گاه داریم:

$T(n) = \Theta\left(n^{\log_b a} \right).$

مثال

$T(n) = 8 T\left(\frac{n}{2}\right) + 1000n^2$

همان طور که در فرمول فوق دیده می‌شود، متغیرها دارای مقادیر زیر هستند:

$a = 8 \,$, $b = 2 \,$, $f(n) = 1000n^2 \,$, $\log_b a = \log_2 8 = 3 \,$

حال باید برقراری معادلهٔ زیر را بررسی کنیم:

$f(n) = \mathcal{O}\left(n^{\log_b a - \epsilon} \right)$

اگر مقادیر متغیرها را در این رابطه جایگزین کنیم، خواهیم داشت:

$1000n^2 = \mathcal{O}\left(n^{3 - \epsilon} \right)$

با انتخاب $\epsilon =1$ داریم:

$1000n^2 = \mathcal{O}\left(n^{3 - 1} \right) = \mathcal{O}\left(n^{2} \right)$

از آن جایی که معادلهٔ بالا برقرار است، حالت اول قضیهٔ اصلی را برای رابطهٔ بازگشنی به کار می‌بریم و از نتیجهٔ زیر استفاده می‌کنیم:

$T(n) = \Theta\left(n^{\log_b a} \right).$

اگر مقادیر فوق را در رابطهٔ بالا قرار دهیم، در نهایت خواهیم داشت:

$T(n) = \Theta\left(n^{3} \right).$

از این رو رابطهٔ بازگشتی داده شده (T(n از(Θ(n³ است.

(راه حل دقیق رابطهٔ بازگشتی نیز این نتیجه را تأیید می‌کند، که در آن $T(n) = 1001 n^3 - 1000 n^2$، بافرض $T(1) = 1$ است.)

حالت ۲

شکل کلی

اگر داشته باشیم:

$\exists k\ge 0, f(n) = \Theta\left(n^{\log_b a} \log^{k} n \right)$

آن گاه خواهیم داشت:

$T(n) = \Theta\left(n^{\log_b a} \log^{k+1} n \right).$

مثال

$T(n) = 2 T\left(\frac{n}{2}\right) + 10n$

همان طور که در فرمول فوق مشاهده می‌شود، متغیرها مقادیر زیر را اختیار می‌کنند:

$a = 2 \,$, $b = 2 \,$, $k = 0 \,$, $f(n) = 10n \,$, $\log_b a = \log_2 2 = 1 \,$

حال می‌بایست برقراری رابطهٔ زیر را بررسی کنیم (در حالتی که k=۰ باشد):

$f(n) = \Theta\left(n^{\log_b a} \right)$

اگر مفادیر متغیرها را از رابطهٔ بالا در این رابطه جایگزین کنیم، خواهیم داشت:

$10n = \Theta\left(n^{1} \right) = \Theta\left(n \right)$

از آن جایی که این رابطه برقرار است، حالت دوم قضیهٔ اصلی را برای رابطهٔ بازگشنی به کار می‌بریم و از نتیجهٔ زیر استفاده می‌کنیم:

$T(n) = \Theta\left(n^{\log_b a} \log n\right).$

با جایگزین کردن مقادیر فوق در این رابطه در نهایت خواهیم داشت:

$T(n) = \Theta\left(n \log n\right).$

از این رو رابطهٔ بازگشتی داده شدهٔ (T(n از (Θ(n log n است.

(راه حل دقیق رابطهٔ بازگشتی نیز این نتیجه را تأیید می‌کند، که در آن $T(n) = n + 10 n\log_2 n$، بافرض $T(1) = 1$ است.)

حالت ۳

شکل کلی

اگر ثابت $\epsilon > 0$ وجود داشته باشد به طوری که رابطهٔ $f(n) = \Omega\left(n^{\log_b a + \epsilon} \right)$ برقرار باشد و هم چنین اگر برای n‌های به اندازهٔ کافی بزرگ ثابت $c<1$ وجود داشته باشد به گونه‌ای که رابطه زیر برقرار باشد:

$a f\left(\frac{n}{b} \right) \le c f(n)$

آنگاه خواهیم داشت:

$T\left(n \right) = \Theta \left(f \left(n \right) \right).$

مثال

$T(n) = 2 T\left(\frac{n}{2}\right) + n^2$

همان طور که در فرمول فوق دیده می‌شود، متغیرها مقادیر زیر را اختیار می‌کنند:

$a = 2 \,$, $b = 2 \,$, $f(n) = n^2 \,$, $\log_b a = \log_2 2 = 1 \,$

حال می‌بایست برقراری معادلهٔ زیر را مورد بررسی قرار دهیم:

$f(n) = \Omega\left(n^{\log_b a + \epsilon} \right)$

اگر مقادیر متغیرها را طبق روابط بالا قرار دهیم و مقدار $\epsilon =1$ را انتخاب کنیم، خواهیم داشت:

$n^2 = \Omega\left(n^{1 + 1} \right) = \Omega\left(n^2 \right)$

از آن جایی که معادلهٔ فوق برقرار است، حال باید شرط دوم را مورد بررسی قرار دهیم. به عبارت دیگر باید درستی رابطهٔ زیر را مورد بررسی قرار دهیم:

$a f\left(\frac{n}{b} \right) \le c f(n)$

اگر بار دیگر مقادیر متغیرها را طبق روابط بالا قرار دهیم، خواهیم داشت:

$\le c n^2 \Leftrightarrow \frac{1}{2} n^2 \le cn^2$ $2 \left(\frac{n}{2} \right)^2$

اگر $c = \frac{1}{2}$ را برگزینیم، آن گاه:

$\forall n \ge 1$ $\frac{1}{2} n^2 \le \frac{1}{2} n^2$

پس خواهیم داشت:

$T \left(n \right) = \Theta \left(f \left(n \right) \right).$

اگر بار دیگر مقادیر لازم را قرار دهیم، رابطهٔ زیر به دست می‌آید:

$T \left(n \right) = \Theta \left(n^2 \right).$

از این رو رابطهٔ بازگشتی داده شده (T(n از (Θ(n² است.

(راه حل دقیق رابطهٔ بازگشتی نیز این نتیجه را تأیید می‌کند، که در آن $T(n) = 2 n^2 - n$، بافرض $T(1) = 1$ است.)

حالت‌های غیر قابل قبول

معادلات زیر را نمی‌توان با استفاده از قضیهٔ اصلی حل کرد:

$T(n) = 2^nT\left (\frac{n}{2}\right)+n^n$

a مقدار ثابت نیست.

$T(n) = 2T\left (\frac{n}{2}\right)+\frac{n}{\log n}$

اختلاف بین (f(n و $n^{\log_b a}$ غیر چندجمله‌ای است.

$T(n) = 0.5T\left (\frac{n}{2}\right)+n$

a<۱ است درحالی که نمی‌توان کم تر از یک زیر مسأله داشت.

$T(n) = 64T\left (\frac{n}{8}\right)-n^2\log n$:

(f(n مثبت نیست.

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

• علامت O بزرگ

منابع

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.
• Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. ISBN 0-471-38365-1. The master theorem (including the version of Case 2 included here, which is stronger than the one from CLRS) is on pp. 268–270.
• مشارکت‌کنندگان ویکی‌پدیا، «Master theorem»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۳ می ۲۰۱۱).