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

لینک دوستان

ارشیو

فروشگاه سی شارپ

فروشگاه کدهای php

فروشگاه asp.net

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

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

شکل کلی

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

$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) = Thetaleft(n^{log_b a} right).$

مثال

$T(n) = 8 Tleft(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) = Thetaleft(n^{log_b a} right).$

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

$T(n) = Thetaleft(n^{3} right).$

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

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

حالت ۲

شکل کلی

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

$exists kge 0, f(n) = Thetaleft(n^{log_b a} log^{k} n right)$

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

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

مثال:

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

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

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

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

$f(n) = Thetaleft(n^{log_b a} right)$

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

$10n = Thetaleft(n^{1} right) = Thetaleft(n right)$

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

$T(n) = Thetaleft(n^{log_b a} log nright).$

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

$T(n) = Thetaleft(n log nright).$

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

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

حالت ۳

شکل کلی

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