موضوع مقاله: قضیه اصلی (تحلیل الگوریتم‌ها) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # قضیه اصلی (تحلیل الگوریتم‌ها) | مقدمه: در تحلیل الگوریتم‌ها، قضیه اصلی برای تحلیل مجانبی بسیاری از الگوریتم‌های تقسیم و حل استفاده می‌شود. | ## بخش 1: قضیه اصلی (تحلیل الگوریتم‌ها) | در این نوع از الگوریتم‌ها معمولاً می‌توان یک رابطهٔ بازگشتی برای توصیف زمان اجرای آنها پیدا کرد. شکل کلی قضیه اصلی یک روش سرراست برای حل روابط بازگشتی به فرم زیر ارائه می‌کند: با فرض این که و و باشند. این رابطهٔ بازگشتی زمان اجرای الگوریتمی را توصیف می‌کند که مسأله‌ای به اندازهٔ را به زیرمسأله (همگی به اندازهٔ تقریبی ) تقسیم می‌کند. در این صورت قضیه اصلی بیان می‌کند که: +حالتشرط شرح قضیه۱اگر آنگاه خواهد بود.۲اگر باشددر آن صورت می‌شود.۳اگر و همچین شرط حالت طبیعی زیر برقرار باشد می‌شود. این شکاف زمانی پیش می‌آید که از بزرگتر (یا کوچکتر) باشد ولی مقدار بزرگتر (یا کوچکتر) بودنش به صورت چندجمله‌ای نباشد. در این صورت گاهی می‌توان از یک تعمیم کوچک برای حالت ۲ استفاده کرد: حالتشرط شرط شرح قضیه۲ الفاگر باشدبه ازای هر آنگاه خواهد بود.۲ بو باشددر آن صورت می‌شود.۲ جبه شرط می‌شود. | ## بخش 2: قضیه اصلی (تحلیل الگوریتم‌ها) | مثال برای پیدا کردن پیچیدگی جستجوی دودویی یا مرتب‌سازی ادغامی و بسیاری از الگوریتم‌های دیگر می‌توان از این قضیه استفاده کرد. (راه حل دقیق رابطهٔ بازگشتی نیز این نتیجه را تأیید می‌کند، که در آن ، بافرض است.) حالت ۳ همان طور که در فرمول فوق دیده می‌شود، متغیرها مقادیر زیر را اختیار می‌کنند: ، ، ، حال می‌بایست برقراری معادلهٔ زیر را مورد بررسی قرار دهیم: اگر مقادیر متغیرها را طبق روابط بالا قرار دهیم و مقدار را انتخاب کنیم، خواهیم داشت: از آن جایی که معادلهٔ فوق برقرار است، حال باید شرط دوم را مورد بررسی قرار دهیم. به عبارت دیگر باید درستی رابطهٔ زیر را مورد بررسی قرار دهیم: اگر بار دیگر مقادیر متغیرها را طبق روابط بالا قرار دهیم، خواهیم داشت: اگر را برگزینیم، آن گاه: پس خواهیم داشت: اگر بار دیگر مقادیر لازم را قرار دهیم، رابطهٔ زیر به دست می‌آید: از این رو رابطهٔ بازگشتی داده شده (T(n از (Θ(n² است. (راه حل دقیق رابطهٔ بازگشتی نیز این نتیجه را تأیید می‌کند، که در آن ، بافرض است.) در روش درخت بازگشتی ، کل کارهای انجام شده را محاسبه می کنیم. اگر کارهایی که در برگها انجام می شود چند جمله ای بیشتری است ، پس برگها قسمت اصلی هستند و نتیجه ما به کارهایی که در برگها انجام می شود تبدیل می شود (حالت 1). اگر کارهایی که در برگ و ریشه انجام می شود به صورت یکسان باشد ، نتیجه کار ما با کارهایی که در هر سطح انجام می شود ضرب می شود (حالت 2). | ## بخش 3: قضیه اصلی (تحلیل الگوریتم‌ها) | اگر کارهایی که در ریشه انجام می شوند بیشتر از لحاظ غیرمتعارف باشند ، نتیجه ما به کارهایی در ریشه انجام می شود (حالت 3). حالت‌های ناپذیرفتنی معادلات زیر را نمی‌توان با استفاده از قضیهٔ اصلی حل کرد: a مقدار ثابت نیست. صحت قضیه اصلی نشان دادن درست بودن این قضیه در حالت کلی کار ساده ای نیست اما در ادامه صحت این قضیه را برای یک حالت خاص بررسی می کنیم. برای هر سطح در درخت هزینه های زیر را داریم : هزینه ی رأسها در سطح ۱: هزینه ی رأسها در سطح ۲: ... هزینه ی رأسها در سطحi : برای محاسبه هزینه کل ، هزینه های هر سطح را با هم جمع میزنیم.( تحلیل سرشکن ) مقدار رأس ریشه در درخت برابرnd است. به جز راسهای برگ ، هر رأس در این درختa فرزند دارد که مقدار هرکدامb )-d ) برابر مقدار پدرش است؛ یعنی به عنوان مثال فرزندان ریشه مقداری برابر دارند. | ## جمع‌بندی | با محاسبه جمع مقادیر سطوح مختلف درخت به مجموع کل میرسیم: که این مقدار هزینهی متناظر با ریشه (T(n است را تعیین میکند.