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

قضیه اصلی واکاوی (تحلیل) الگوریتم‌ها که حالتی خاص از روش اکرا-بازی است در تحلیل الگوریتم‌ها، یک راه حل سرراست برای حالت‌های مجانبی که در عمل در انواع روابط بازگشتی رخ می‌دهند، ارائه می‌کند. این قضیه با کتاب درسی معروف مقدمه‌ای بر الگوریتم‌ها نوشته کرمن، لیسرسن، ریوست و استین به شهرت رسید. این قضیه در بخش ۴٫۳ دراین کتاب معرفی شده‌است و متعاقبا در بخش ۴٫۴ به اثبات رسیده‌است. هرچند که نمی‌توان تمامی روابط بازگشتی را به کمک قضیه اصلی حل کرد.
شکل کلی
قضیه اصلی روابطی را مورد بررسی قرار می‌دهد که به شکل زیر باشند:
در استفاده از رابطه فوق برای یک الگوریتم بازگشتی معنای علائم به کار رفته، به شرح زیر است: *n اندازه مسئله‌است.
a تعداد زیرمسئله هاست.
n/b اندازه هر یک از زیرمسئله هاست. (در اینجا فرض شده‌است که اندازه همه زیرمسئله‌ها با هم برابر است.)
(f(n هزینه بخش غیر بازگشتی است که شامل هزینه تقسیم مسئله به زیرمسئله‌ها و هزینه ادغام پاسخ به زیرمسئله هاست.
در سه حالت می‌توان یک حد مجانبی مشخص کرد:
حالت ۱
شکل کلی
اگر ثابت وجود داشته باشد به طوری که رابطه برقرار باشد،
آن گاه داریم:
مثال اول
همان طور که در فرمول فوق دیده می‌شود، متغیرها دارای مقادیر زیر هستند:
حال باید برقراری معادله زیر را بررسی کنیم:
اگر مقادیر متغیرها را در این رابطه جایگزین کنیم، خواهیم داشت:
با انتخاب داریم:
از آن جایی که معادله بالا برقرار است، حالت اول قضیه اصلی را برای رابطه بازگشنی به کار می‌بریم و از نتیجه زیر استفاده می‌کنیم:
اگر مقادیر فوق را در رابطه بالا قرار دهیم، در نهایت خواهیم داشت:
از این رو رابطه بازگشتی داده شده (T(n از((n3 است.
(راه حل دقیق رابطه بازگشتی نیز این نتیجه را تایید می‌کند، که در آن ، بافرض است.)
حالت ۲
شکل کلی
اگر داشته باشیم:
آن گاه خواهیم داشت:
مثال
همان طور که در فرمول فوق مشاهده می‌شود، متغیرها مقادیر زیر را اختیار می‌کنند:
حال می‌بایست برقراری رابطه زیر را بررسی کنیم (در حالتی که k=۰ باشد):
اگر مفادیر متغیرها را از رابطه بالا در این رابطه جایگزین کنیم، خواهیم داشت:
از آن جایی که این رابطه برقرار است، حالت دوم قضیه اصلی را برای رابطه بازگشنی به کار می‌بریم و از نتیجه زیر استفاده می‌کنیم:
با جایگزین کردن مقادیر فوق در این رابطه در نهایت خواهیم داشت:
از این رو رابطه بازگشتی داده شده (T(n از ((n log n است.
(راه حل دقیق رابطه بازگشتی نیز این نتیجه را تایید می‌کند، که در آن ، بافرض است.)
حالت ۳
شکل کلی
اگر ثابت وجود داشته باشد به طوری که رابطه برقرار باشد و هم چنین اگر برای nهای به اندازه کافی بزرگ ثابت وجود داشته باشد به گونه‌ای که رابطه زیر برقرار باشد:
آنگاه خواهیم داشت:
مثال
همان طور که در فرمول فوق دیده می‌شود، متغیرها مقادیر زیر را اختیار می‌کنند:
حال می‌بایست برقراری معادله زیر را مورد بررسی قرار دهیم:
اگر مقادیر متغیرها را طبق روابط بالا قرار دهیم و مقدار را انتخاب کنیم، خواهیم داشت:
از آن جایی که معادله فوق برقرار است، حال باید شرط دوم را مورد بررسی قرار دهیم. به عبارت دیگر باید درستی رابطه زیر را مورد بررسی قرار دهیم:
اگر بار دیگر مقادیر متغیرها را طبق روابط بالا قرار دهیم، خواهیم داشت:
اگر را برگزینیم، آن گاه:
پس خواهیم داشت:
اگر بار دیگر مقادیر لازم را قرار دهیم، رابطه زیر به دست می‌آید:
از این رو رابطه بازگشتی داده شده (T(n از ((n2 است.
(راه حل دقیق رابطه بازگشتی نیز این نتیجه را تایید می‌کند، که در آن ، بافرض است.)
حالت‌های غیر قابل قبول
معادلات زیر را نمی‌توان با استفاده از قضیه اصلی حل کرد:
a مقدار ثابت نیست.
اختلاف بین (f(n و غیر چندجمله‌ای است.
a<۱ است درحالی که نمی‌توان کم‌تر از یک زیر مسئله داشت.
(f(n مثبت نیست.
علامت O بزرگ