قضیه اصلی (تحلیل الگوریتم‌ها)

در تحلیل الگوریتم‌ها، قضیه اصلی برای تحلیل مجانبی بسیاری از الگوریتم‌های تقسیم و حل استفاده می‌شود. در این نوع از الگوریتم‌ها معمولاً می‌توان یک رابطهٔ بازگشتی برای توصیف زمان اجرای آنها پیدا کرد. برای توصیف پیچیدگی چنین رابطه‌ای (به کمک نماد $\mathrm{\Theta }$) از این قضیه استفاده می‌شود.

البته نمی‌توان هر رابطهٔ بازگشتی را به کمک این قضیه حل کرد. روش اکرا-بازی تعمیمی از این قضیه است. این قضیه با کتاب معروف مقدمه‌ای بر الگوریتم‌ها به شهرت رسید.

شکل کلی

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

$T(n)=aT\left(\left[\frac{n}{b}\right]\right)+f(n)$

با فرض این که $b>1$ و $a>0$ و $f(n)⩾0$ باشند.

این رابطهٔ بازگشتی زمان اجرای الگوریتمی را توصیف می‌کند $T(n)$ که مسأله‌ای به اندازهٔ $n$ را به $a$ زیرمسأله (همگی به اندازهٔ تقریبی $\frac{n}{b}$) تقسیم می‌کند. همچنین $f(n)$ هزینهٔ تقسیم و ترکیب زیرمسائل است.

مقدار توان بحرانی $c_{\text{crit}}$ را به صورت $c_{\text{crit}}={\log }_{b}a$ تعریف می‌کنیم. در این صورت قضیه اصلی بیان می‌کند که:

حالت	شرط $f(n)$	شرح قضیه
۱	اگر $\mathrm{\exists }c<c_{\text{crit}}:f\in 𝒪(n^c)$	آنگاه $T(n)\in \mathrm{\Theta }\left(n^{c_{\text{crit}}}\right)$ خواهد بود.
۲	اگر $f\in \mathrm{\Theta }(n^{c_{\text{crit}}})$ باشد	در آن صورت $T(n)\in \mathrm{\Theta }(n^{c_{\text{crit}}}\lg n)$ می‌شود.
۳	اگر $\mathrm{\exists }c>c_{\text{crit}}:f\in \mathrm{\Omega }(n^c)$و همچین شرط حالت طبیعی زیر برقرار باشد$\mathrm{\exists }{n}_0,k<1:\mathrm{\forall }n⩾n_0:af\left(\frac{n}{b}\right)⩽kf(n)$	$T(n)\in \mathrm{\Theta }(f(n))$ می‌شود.

توجه کنید این سه حالت بعضی حالت‌های ممکن برای $f(n)$ را پوشش نمی‌دهند. یک شکاف بین حالت ۲ و ۳ (و همچنین بین حالات ۱ و ۲) وجود دارد. به عنوان مثال $f=n^{c_{\text{crit}}}\lg n$ بین حالات ۲ و ۳ قرار می‌گیرد (یا $f=n^{c_{\text{crit}}}/\lg n$ بین ۱ و ۲). این شکاف زمانی پیش می‌آید که $f(n)$ از $n^{c_{\text{crit}}}$ بزرگتر (یا کوچکتر) باشد ولی مقدار بزرگتر (یا کوچکتر) بودنش به صورت چندجمله‌ای نباشد. در این صورت گاهی می‌توان از یک تعمیم کوچک برای حالت ۲ استفاده کرد:

حالت	شرط $f(n)$	شرط $k$	شرح قضیه
۲ الف	اگر $f\in \mathrm{\Theta }(n^{c_{\text{crit}}}{\lg }^{k}n)$ باشد	به ازای هر $k>-1$	آنگاه $T(n)\in \mathrm{\Theta }(n^{c_{\text{crit}}}{\lg }^{k+1}n)$ خواهد بود.
۲ ب		و $k=-1$ باشد	در آن صورت $T(n)\in \mathrm{\Theta }(n^{c_{\text{crit}}}\lg \lg n)$ می‌شود.
۲ ج		به شرط $k<-1$	$T(n)\in \mathrm{\Theta }(n^{c_{\text{crit}}})$ می‌شود.

مثال

برای پیدا کردن پیچیدگی جستجوی دودویی یا مرتب‌سازی ادغامی و بسیاری از الگوریتم‌های دیگر می‌توان از این قضیه استفاده کرد.

حالت ۱

الگو:وسط‌چین $T(n)=8T\left(\frac{n}{2}\right)+1000n^2$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $a=8$، $b=2$، $f(n)=1000n^2$، ${\log }_{b}a={\log }_{2}8=3$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $f(n)=𝒪\left(n^{{\log }_{b}a-ϵ}\right)$ الگو:پایان وسط‌چین

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

درخت بازگشت

$1000n^2=𝒪\left(n^{3-ϵ}\right)$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $1000n^2=𝒪\left(n^{3-1}\right)=𝒪\left(n^2\right)$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $T(n)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right).$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $T(n)=\mathrm{\Theta }\left(n^3\right).$ الگو:پایان وسط‌چین

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

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

حالت ۲

الگو:وسط‌چین $T(n)=2T\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)=\mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $10n=\mathrm{\Theta }\left(n^1\right)=\mathrm{\Theta }\left(n\right)$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log n).$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $T(n)=\mathrm{\Theta }(n\log n).$ الگو:پایان وسط‌چین

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

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

حالت ۳

الگو:وسط‌چین $T(n)=2T\left(\frac{n}{2}\right)+n^2$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $a=2$، $b=2$، $f(n)=n^2$، ${\log }_{b}a={\log }_{2}2=1$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $f(n)=\mathrm{\Omega }\left(n^{{\log }_{b}a+ϵ}\right)$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $n^2=\mathrm{\Omega }\left(n^{1+1}\right)=\mathrm{\Omega }\left(n^2\right)$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $af\left(\frac{n}{b}\right)\le cf(n)$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $\le c{n}^2\iff \frac{1}{2}{n}^2\le c{n}^2$ $2{\left(\frac{n}{2}\right)}^2$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $\mathrm{\forall }n\ge 1$ $\frac{1}{2}{n}^2\le \frac{1}{2}{n}^2$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $T\left(n\right)=\mathrm{\Theta }\left(f\left(n\right)\right).$ الگو:پایان وسط‌چین

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

الگو:وسط‌چین $T\left(n\right)=\mathrm{\Theta }\left(n^2\right).$ الگو:پایان وسط‌چین

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

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

در روش درخت بازگشتی ، کل کارهای انجام شده را محاسبه می کنیم. اگر کارهایی که در برگها انجام می شود چند جمله ای بیشتری است ، پس برگها قسمت اصلی هستند و نتیجه ما به کارهایی که در برگها انجام می شود تبدیل می شود (حالت 1). اگر کارهایی که در برگ و ریشه انجام می شود به صورت یکسان باشد ، نتیجه کار ما با کارهایی که در هر سطح انجام می شود ضرب می شود (حالت 2). اگر کارهایی که در ریشه انجام می شوند بیشتر از لحاظ غیرمتعارف باشند ، نتیجه ما به کارهایی در ریشه انجام می شود (حالت 3).

حالت‌های ناپذیرفتنی

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

الگو:وسط‌چین $T(n)=2^{n}T\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 مثبت نیست.

صحت قضیه اصلی

نشان دادن درست بودن این قضیه در حالت کلی کار ساده ای نیست اما در ادامه صحت این قضیه را برای یک حالت خاص بررسی می کنیم.

فرض می کنیم ^(f(n تابعی از مرتبه چندجمله ای باشد یعنی ^{(f(n) = Θ(nd} آنگاه :

$T(n)=aT\left(\frac{n}{b}\right)+n^d$

پس داریم :

log_b a > d −→ T(n) = Θ(n^logbb ^a)

log_b a = d −→ T(n) = Θ(n^{log a})

log_b a < d −→ T(n) = Θ(n^d)

میخواهیم مجموع هزینه ها را به دست بیاوریم پس درخت بازگشت آن را رسم میکنیم. برای هر سطح در درخت هزینه های زیر را داریم :

هزینه ی رأسها در سطح ۱:$c{n}^d$

هزینه ی رأسها در سطح ۲: $ac{\left(\frac{n}{b}\right)}^d$

...

هزینه ی رأسها در سطحi :$a^{i-1}c{\left(\frac{n}{b^{i-1}}\right)}^d$

برای محاسبه هزینه کل ، هزینه های هر سطح را با هم جمع میزنیم.( تحلیل سرشکن )

مقدار رأس ریشه در درخت برابرn^d  است. به جز راسهای برگ ، هر رأس در این درختa  فرزند دارد که مقدار هرکدام_b )^-d ) برابر مقدار پدرش است؛ یعنی به عنوان مثال فرزندان ریشه مقداری برابر${\left(\frac{n}{b}\right)}^d$  دارند. و هزینهی هر برگc است.  

با محاسبه جمع مقادیر سطوح مختلف درخت به مجموع کل میرسیم:

$T(n)\le \sum _{i=0}^{\log \left(\frac{n}{b}\right)-1}C{a}^i{\left(\frac{n}{b^i}\right)}^d+\theta (n^{{\log }_{b}a})$

که این مقدار هزینهی متناظر با ریشه (T(n است را تعیین میکند.

قضیه اصلی برای تفریق و حل بازگشتی

قضیه اصلی واکاوی الگوریتم‌ها برای تعیین کارکردهای دارای محدودیت بالایی Big - O استفاده می شود ، که می تواند در مسایل فرعی شکسته شود.قضیه اصلی برای تکرار تفریق و تقسیم:بگذارید T (n) تابعی باشد که مطابق شکل زیر در n مثبت نشان داده شده است:

قضیه اصلی برای تفریق و حل بازگشتی:

قضیه اصلی برای منها کردن

فرض کنید T (n) تابعی باشد که مطابق شکل در n مثبت نشان داده شده است:

1. If a<1 then T(n) = O(n^k)

2. If a=1 then T(n) = O(n^k+1)

3. if a>1 then T(n) = O(n^ka^n/b)

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

• علامت O بزرگ

منابع

الگو:پانویس الگو:چپ‌چین.

• Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundation, Analysis, and Internet Examples. Wiley, 2002. الگو:شابک. The master theorem (including the version of Case 2 included here, which is stronger than the one from CLRS) is on pp. 268–270.
• الگو:یادکرد-ویکی