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

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

) از این قضیه استفاده می‌شود.

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

شکل کلی

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

$T(n)=a\;T\!\left(\left[{n \over b}\right]\right)+f(n)$

با فرض این که $b>1$

و

a>0

و

f(n)\geqslant 0

باشند.

این رابطهٔ بازگشتی زمان اجرای الگوریتمی را توصیف می‌کند $T(n)$

که مسأله‌ای به اندازهٔ

n

را به

a

زیرمسأله (همگی به اندازهٔ تقریبی

{n \over b}

) تقسیم می‌کند. همچنین

f(n)

هزینهٔ تقسیم و ترکیب زیرمسائل است.

مقدار توان بحرانی $c_{\text{crit}}$

را به صورت

c_{\text{crit}}=\log _{b}a

تعریف می‌کنیم. در این صورت قضیه اصلی بیان می‌کند که:


حالت	شرط $f(n)$	شرح قضیه
۱	اگر $\exists c<c_{\text{crit}}:f\in {\mathcal {O}}(n^{c})$	آنگاه $T(n)\in \Theta \!\left(n^{c_{\text{crit}}}\right)$ خواهد بود.
۲	اگر $f\in \Theta (n^{c_{\text{crit}}})$ باشد	در آن صورت $T(n)\in \Theta (n^{c_{\text{crit}}}\lg n)$ می‌شود.
۳	اگر $\exists c>c_{\text{crit}}:f\in \Omega (n^{c})$ و همچین شرط حالت طبیعی زیر برقرار باشد $\exists n_{0},k<1:\forall n\geqslant n_{0}:af\left({\frac {n}{b}}\right)\leqslant kf(n)$	$T(n)\in \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 \Theta (n^{c_{\text{crit}}}\lg ^{k}n)$ باشد	به ازای هر $k>-1$	آنگاه $T(n)\in \Theta (n^{c_{\text{crit}}}\lg ^{k+1}n)$ خواهد بود.
۲ ب		و $k=-1$ باشد	در آن صورت $T(n)\in \Theta (n^{c_{\text{crit}}}\lg \lg n)$ می‌شود.
۲ ج		به شرط $k<-1$	$T(n)\in \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)={\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)=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)=\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+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)=\Omega \left(n^{\log _{b}a+\epsilon }\right)$

اگر مقادیر متغیرها را طبق روابط بالا قرار دهیم و مقدار $\epsilon =1$

را انتخاب کنیم، خواهیم داشت:

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

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

$af\left({\frac {n}{b}}\right)\leq cf(n)$

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

$\leq cn^{2}\Leftrightarrow {\frac {1}{2}}n^{2}\leq cn^{2}$

2\left({\frac {n}{2}}\right)^{2}

اگر $c={\frac {1}{2}}$

را برگزینیم، آن گاه:

$\forall n\geq 1$

{\frac {1}{2}}n^{2}\leq {\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)=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 مثبت نیست.

صحت قضیه اصلی

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

فرض می کنیم تابعی از مرتبه چندجمله ای باشد یعنی آنگاه :

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

پس داریم :

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

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

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

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

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

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

...

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

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

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

دارند. و هزینهی هر برگc است.

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

$T(n)\leq \sum _{i=0}^{\log {\left({\frac {n}{b}}\right)}-1}Ca^{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)

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

3. if a>1 then T(n) = O(na)

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

علامت O بزرگ

منابع

↑ Introduction to Algorithms (CLRS) (3rd edition). به کوشش Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein.
↑ A real elementary approach to the master recurrence and generalizations. به کوشش Chee Yap. ص. ۱۴–۲۶.
↑ Yash Singla (5/16/2020). "Master Theorem For Subtract and Conquer Recurrences". www.geeksforgeeks.org (به انگلیسی).

.

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.

[:02-1] Introduction to Algorithms (CLRS) (3rd edition). به کوشش Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein.

[2] A real elementary approach to the master recurrence and generalizations. به کوشش Chee Yap. ص. ۱۴–۲۶.

[3] Yash Singla (5/16/2020). "Master Theorem For Subtract and Conquer Recurrences". www.geeksforgeeks.org (به انگلیسی).