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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

شکل کلی[ویرایش]

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

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 مثبت نیست.

جستارهای وابسته[ویرایش]

منابع[ویرایش]