قضیه اصلی (تحلیل الگوریتم‌ها) کیست؟ توضیح بده.
در تحلیل الگوریتم‌ها، قضیه اصلی برای تحلیل مجانبی بسیاری از الگوریتم‌های تقسیم و حل استفاده می‌شود. در این نوع از الگوریتم‌ها معمولاً می‌توان یک رابطهٔ بازگشتی برای توصیف زمان اجرای آنها پیدا کرد. برای توصیف پیچیدگی چنین رابطه‌ای (به کمک نماد formula_1) از این قضیه استفاده می‌شود.البته نمی‌توان هر رابطهٔ بازگشتی را به کمک این قضیه حل کرد. روش اکرا-بازی تعمیمی از این قضیه است. این قضیه با کتاب معروف "مقدمه‌ای بر الگوریتم‌ها" به شهرت رسید.شکل کلی.قضیه اصلی یک روش سرراست برای حل روابط بازگشتی به فرم زیر ارائه می‌کند:formula_2با فرض این که formula_3 و formula_4 و formula_5 باشند.این رابطهٔ بازگشتی زمان اجرای الگوریتمی را توصیف می‌کند formula_6 که مسأله‌ای به اندازهٔ formula_7 را به formula_8 زیرمسأله (همگی به اندازهٔ تقریبی formula_9) تقسیم می‌کند. همچنین formula_10 هزینهٔ تقسیم و ترکیب زیرمسائل است.مقدار "توان بحرانی" formula_11 را به صورت formula_12 تعریف می‌کنیم. در این صورت قضیه اصلی بیان می‌کند که:توجه کنید این سه حالت بعضی حالت‌های ممکن برای formula_10 را پوشش نمی‌دهند. یک شکاف بین حالت ۲ و ۳ (و همچنین بین حالات ۱ و ۲) وجود دارد. به عنوان مثال formula_14 بین حالات ۲ و ۳ قرار می‌گیرد (یا formula_15 بین ۱ و ۲). این شکاف زمانی پیش می‌آید که formula_10 از formula_17 بزرگتر (یا کوچکتر) باشد ولی مقدار بزرگتر (یا کوچکتر) بودنش به صورت چندجمله‌ای نباشد. در این صورت گاهی می‌توان از یک تعمیم کوچک برای حالت ۲ استفاده کرد:مثال.برای پیدا کردن پیچیدگی جستجوی دودویی یا مرتب‌سازی ادغامی و بسیاری از الگوریتم‌های دیگر می‌توان از این قضیه استفاده کرد.حالت ۱.formula_18همان طور که در فرمول فوق دیده می‌شود، متغیرها دارای مقادیر زیر هستند:formula_19، formula_20، formula_21، formula_22حال باید برقراری معادلهٔ زیر را بررسی کنیم:formula_23اگر مقادیر متغیرها را در این رابطه جایگزین کنیم، خواهیم داشت:formula_24با انتخاب formula_25 داریم:formula_26از آن جایی که معادلهٔ بالا برقرار است، حالت اول قضیهٔ اصلی را برای رابطهٔ بازگشتی به کار می‌بریم و از نتیجهٔ زیر استفاده می‌کنیم:formula_27اگر مقادیر فوق را در رابطهٔ بالا قرار دهیم، در نهایت خواهیم داشت:formula_28از این رو رابطهٔ بازگشتی داده شده ("T"("n" از(Θ("n"³ است.حالت ۲.formula_31همان طور که در فرمول فوق مشاهده می‌شود، متغیرها مقادیر زیر را اختیار می‌کنند:formula_32، formula_20، formula_34، formula_35، formula_36حال می‌بایست برقراری رابطهٔ زیر را بررسی کنیم (در حالتی که k=۰ باشد):formula_37اگر مفادیر متغیرها را،از رابطهٔ بالا در این رابطه جایگزین کنیم، خواهیم داشت:formula_38از آن جایی که این رابطه برقرار است، حالت دوم قضیهٔ اصلی را برای رابطهٔ بازگشنی به کار می‌بریم و از نتیجهٔ زیر استفاده می‌کنیم:formula_39با جایگزین کردن مقادیر فوق در این رابطه در نهایت خواهیم داشت:formula_40از این رو رابطهٔ بازگشتی داده شدهٔ ("T"("n" از (Θ("n" log "n" است.حالت ۳.formula_43همان طور که در فرمول فوق دیده می‌شود، متغیرها مقادیر زیر را اختیار می‌کنند:formula_32، formula_20، formula_46، formula_36حال می‌بایست برقراری معادلهٔ زیر را مورد بررسی قرار دهیم:formula_48اگر مقادیر متغیرها را طبق روابط بالا قرار دهیم و مقدار formula_25 را انتخاب کنیم، خواهیم داشت:formula_50از آن جایی که معادلهٔ فوق برقرار است، حال باید شرط دوم را مورد بررسی قرار دهیم. به عبارت دیگر باید درستی رابطهٔ زیر را مورد بررسی قرار دهیم:formula_51اگر بار دیگر مقادیر متغیرها را طبق روابط بالا قرار دهیم، خواهیم داشت:formula_52 formula_53اگر formula_54 را برگزینیم، آن گاه:formula_55 formula_56پس خواهیم داشت:formula_57اگر بار دیگر مقادیر لازم را قرار دهیم، رابطهٔ زیر به دست می‌آید:formula_58از این رو رابطهٔ بازگشتی داده شده ("T"("n" از (Θ("n"² است.در روش درخت بازگشتی ، کل کارهای انجام شده را محاسبه می کنیم. اگر کارهایی که در برگها انجام می شود چند جمله ای بیشتری است ، پس برگها قسمت اصلی هستند و نتیجه ما به کارهایی که در برگها انجام می شود تبدیل می شود (حالت 1). اگر کارهایی که در برگ و ریشه انجام می شود به صورت یکسان باشد ، نتیجه کار ما با کارهایی که در هر سطح انجام می شود ضرب می شود (حالت 2). اگر کارهایی که در ریشه انجام می شوند بیشتر از لحاظ غیرمتعارف باشند ، نتیجه ما به کارهایی در ریشه انجام می شود (حالت 3).حالت‌های ناپذیرفتنی.معادلات زیر را نمی‌توان با استفاده از قضیهٔ اصلی حل کرد:formula_61a مقدار ثابت نیست.formula_62اختلاف بین (f(n و formula_63 غیر چندجمله‌ای است.formula_64"a&lt;۱" است درحالی که نمی‌توان کم تر از یک زیر مسئله داشت.formula_65:(f(n مثبت نیست.صحت قضیه اصلی.نشان دادن درست بودن این قضیه در حالت کلی کار ساده ای نیست اما در ادامه صحت این قضیه را برای یک حالت خاص بررسی می کنیم.فرض می کنیم ("f"("n" تابعی از مرتبه چندجمله ای باشد یعنی ("f"("n") = Θ("nd" آنگاه :formula_66پس داریم :log"b a &gt; d" −→ "T"("n") = Θ("n"log"b""b a")log"b a" = "d" −→ "T"("n") = Θ("n"log "a")log"b a &lt; d" −→ "T"("n") = Θ("nd")میخواهیم مجموع هزینه ها را به دست بیاوریم پس درخت بازگشت آن را رسم میکنیم. برای هر سطح در درخت هزینه های زیر را داریم :هزینه ی رأسها در سطح ۱:formula_67هزینه ی رأسها در سطح ۲: formula_68هزینه ی رأسها در سطحi :formula_69برای محاسبه هزینه کل ، هزینه های هر سطح را با هم جمع میزنیم.( تحلیل سرشکن )مقدار رأس ریشه در درخت برابر"nd" است. به جز راسهای برگ ، هر رأس در این درخت"a" فرزند دارد که مقدار هرکدام"b" )"-d" ) برابر مقدار پدرش است؛ یعنی به عنوان مثال فرزندان ریشه مقداری برابرformula_70 دارند. و هزینهی هر برگ"c" است. با محاسبه جمع مقادیر سطوح مختلف درخت به مجموع کل میرسیم:formula_71که این مقدار هزینهی متناظر با ریشه ("T"("n" است را تعیین میکند.قضیه اصلی برای تفریق و حل بازگشتی.قضیه اصلی واکاوی الگوریتم‌ها برای تعیین کارکردهای دارای محدودیت بالایی Big - O استفاده می شود ، که می تواند در مسایل فرعی شکسته شود.قضیه اصلی برای تکرار تفریق و تقسیم:بگذارید T (n) تابعی باشد که مطابق شکل زیر در n مثبت نشان داده شده است:قضیه اصلی برای تفریق و حل بازگشتی:فرض کنید T (n) تابعی باشد که مطابق شکل در n مثبت نشان داده شده است:1. If a&lt;1 then T(n) = O(nk)2. If a=1 then T(n) = O(nk+1)3. if a&gt;1 then T(n) = O(nkan/b)