قضیه اصلی واکاوی الگوریتم‌ها
قضیه اصلی واکاوی (تحلیل) الگوریتم‌ها که حالتی خاص از روش اکرا-بازی در تحلیل الگوریتم‌ها است ، یک راه حل سرراست برای حالت‌های مجانبی که در عمل برای حل انواع روابط بازگشتی رخ می‌دهند، ارائه می‌کند. این قضیه با کتاب درسی معروف "مقدمه‌ای بر الگوریتم‌ها" نوشتهٔ کرمن، لیسرسن، ریوست و استین به شهرت رسید. این قضیه در بخش ۴٫۳ دراین کتاب معرفی شده‌است و متعاقباً در بخش ۴٫۴ به اثبات رسیده‌است. هرچند که نمی‌توان تمامی روابط بازگشتی را به کمک قضیهٔ اصلی حل کرد.
قضیهٔ اصلی روابطی را مورد بررسی قرار می‌دهد که به شکل زیر باشند: formula_1 معنای علائم به کار رفته در استفاده از رابطهٔ فوق برای یک الگوریتم بازگشتی، به شرح زیر است: *"n" اندازهٔ مسئله‌است.
"a" تعداد زیرمسئله هاست.الگوریتم فوق به صورت بازگشتی مساله را به تعدادی از زیرشاخه ها تقسیم می کند که هر یک از مسایل فرعی با اندازه ( n / b ) است . درخت حل آن گره ای برای هر تماس بازگشتی دارد که فرزندان آن گره سایر تماس های حاصل از آن تماس هستند. برگهای درخت موارد اصلی بازگشت هستند ، مقادیر کوچک (از اندازه کمتر از k) که برگشت نمی کنند.
قضیه اصلی واکاوی غالباً مرزهایی را به صورت نامتعارفی به برخی از الگوریتم های تقسیم و به صورت بازگشتی می دهد که یک پارتیشن ورودی را به مقادیر کوچکتر با اندازه های مساوی تقسیم می کند ، مقادیر کوچک فرعی را به صورت بازگشتی حل می کند ، و سپس راه حل های فرعی را با هم ترکیب می کند تا راه حلی برای مسئله اصلی ارائه دهد. زمان چنین الگوریتمی را می توان با اضافه کردن کارهایی که در سطح بالای بازگشت آنها (برای تقسیم مشکلات در زیرمجموعه ها و سپس ترکیب راه حل های فرعی) بیان شده و همزمان با زمان انجام شده در تماس های بازگشتی الگوریتم,انجام می دهند.
طبق قضیه اصلی سه حالت داریم :
1. f(n) = Θ(n) در حالی که c < Loga نتیجه می شود T(n) = Θ(n)
2. If f(n) = Θ(n) در حالی که c = Loga نتیجه می شود T(n) = Θ(nLog n)
3.If f(n) = Θ(n) در حالی کهc > Loga نتیجه می شود T(n) = Θ(f(n))
در سه حالت می‌توان یک حد مجانبی مشخص کرد:
اگر شرط formula_2 وجود داشته باشد به طوری که رابطهٔ formula_3 برقرار باشد،
آن گاه داریم: formula_4 formula_5 همان طور که در فرمول فوق دیده می‌شود، متغیرها دارای مقادیر زیر هستند: formula_6، formula_7، formula_8، formula_9 حال باید برقراری معادلهٔ زیر را بررسی کنیم: formula_10 اگر مقادیر متغیرها را در این رابطه جایگزین کنیم، خواهیم داشت: formula_11 با انتخاب formula_12 داریم: formula_13 از آن جایی که معادلهٔ بالا برقرار است، حالت اول قضیهٔ اصلی را برای رابطهٔ بازگشتی به کار می‌بریم و از نتیجهٔ زیر استفاده می‌کنیم: formula_4 اگر مقادیر فوق را در رابطهٔ بالا قرار دهیم، در نهایت خواهیم داشت: formula_15 از این رو رابطهٔ بازگشتی داده شده ("T"("n" از(Θ("n"³ است.اگر داشته باشیم: formula_18 آن گاه خواهیم داشت: formula_19 formula_20 همان طور که در فرمول فوق مشاهده می‌شود، متغیرها مقادیر زیر را اختیار می‌کنند: formula_21، formula_7، formula_23، formula_24، formula_25 حال می‌بایست برقراری رابطهٔ زیر را بررسی کنیم (در حالتی که k=۰ باشد): formula_26 اگر مفادیر متغیرها را،از رابطهٔ بالا در این رابطه جایگزین کنیم، خواهیم داشت: formula_27 از آن جایی که این رابطه برقرار است، حالت دوم قضیهٔ اصلی را برای رابطهٔ بازگشنی به کار می‌بریم و از نتیجهٔ زیر استفاده می‌کنیم: formula_28 با جایگزین کردن مقادیر فوق در این رابطه در نهایت خواهیم داشت: formula_29 از این رو رابطهٔ بازگشتی داده شدهٔ ("T"("n" از (Θ("n" log "n" است.
اگر شرط formula_2 وجود داشته باشد به طوری که رابطهٔ formula_33 برقرار باشد و همچنین اگر برای nهای به اندازهٔ کافی بزرگ ثابت formula_34 وجود داشته باشد به گونه‌ای که رابطه زیر برقرار باشد: formula_35 آنگاه خواهیم داشت: formula_36 formula_37 همان طور که در فرمول فوق دیده می‌شود، متغیرها مقادیر زیر را اختیار می‌کنند: formula_21، formula_7، formula_40، formula_25 حال می‌بایست برقراری معادلهٔ زیر را مورد بررسی قرار دهیم: formula_33 اگر مقادیر متغیرها را طبق روابط بالا قرار دهیم و مقدار formula_12 را انتخاب کنیم، خواهیم داشت: formula_44 از آن جایی که معادلهٔ فوق برقرار است، حال باید شرط دوم را مورد بررسی قرار دهیم. به عبارت دیگر باید درستی رابطهٔ زیر را مورد بررسی قرار دهیم: formula_35 اگر بار دیگر مقادیر متغیرها را طبق روابط بالا قرار دهیم، خواهیم داشت: formula_46 formula_47 اگر formula_48 را برگزینیم، آن گاه: formula_49 formula_50 پس خواهیم داشت: formula_51 اگر بار دیگر مقادیر لازم را قرار دهیم، رابطهٔ زیر به دست می‌آید: formula_52 از این رو رابطهٔ بازگشتی داده شده ("T"("n" از (Θ("n"² است.
در روش درخت بازگشتی ، کل کارهای انجام شده را محاسبه می کنیم. اگر کارهایی که در برگها انجام می شود چند جمله ای بیشتری است ، پس برگها قسمت اصلی هستند و نتیجه ما به کارهایی که در برگها انجام می شود تبدیل می شود (حالت 1). اگر کارهایی که در برگ و ریشه انجام می شود به صورت یکسان باشد ، نتیجه کار ما با کارهایی که در هر سطح انجام می شود ضرب می شود (حالت 2). اگر کارهایی که در ریشه انجام می شوند بیشتر از لحاظ غیرمتعارف باشند ، نتیجه ما به کارهایی در ریشه انجام می شود (حالت 3).
معادلات زیر را نمی‌توان با استفاده از قضیهٔ اصلی حل کرد: formula_55
a مقدار ثابت نیست. formula_56
اختلاف بین (f(n و formula_57 غیر چندجمله‌ای است. formula_58
"a d" −→ "T"("n") = Θ("n""b ")
log" a" = "d" −→ "T"("n") = Θ("n")
log" a < d" −→ "T"("n") = Θ("n") میخواهیم مجموع هزینه ها را به دست بیاوریم پس درخت بازگشت آن را رسم میکنیم. برای هر سطح در درخت هزینه های زیر را داریم :
هزینه ی رأسها در سطح ۱:formula_61
هزینه ی رأسها در سطح ۲: formula_62
هزینه ی رأسها در سطحi :formula_63
برای محاسبه هزینه کل ، هزینه های هر سطح را با هم جمع میزنیم.( تحلیل سرشکن )
مقدار رأس ریشه در درخت برابر"n"  است. به جز راسهای برگ ، هر رأس در این درخت"a"  فرزند دارد که مقدار هرکدام"" )"" ) برابر مقدار پدرش است؛ یعنی به عنوان مثال فرزندان ریشه مقداری برابرformula_64  دارند. و هزینهی هر برگ"c" است.
با محاسبه جمع مقادیر سطوح مختلف درخت به مجموع کل میرسیم:
formula_65
که این مقدار هزینهی متناظر با ریشه ("T"("n" است را تعیین میکند.
قضیه اصلی واکاوی الگوریتم‌ها برای تعیین کارکردهای دارای محدودیت بالایی Big - O استفاده می شود ، که می تواند در مسایل فرعی شکسته شود. قضیه اصلی برای تکرار تفریق و تقسیم: بگذارید T (n) تابعی باشد که مطابق شکل زیر در n مثبت نشان داده شده است: قضیه اصلی برای تفریق و حل بازگشتی:
فرض کنید T (n) تابعی باشد که مطابق شکل در n مثبت نشان داده شده است:
1. If a<1 then T(n) = O(n)
2. If a=1 then T(n) = O(n)
3. if a>1 then T(n) = O(na) در حالت کلی روش مشخصی برای بهینه سازی الگوریتم ها وجود ندارد و بهینه سازی الگوریتم ، به خلاقیت نیازمنداست تا بتوان الگوریتمهای با مرتبه زمانی کمتر ارایه داد. با بررسی چند مثال روشهایی در این زمینه را معرفی میکنیم . در ابتدا الگوریتم متداول برای حاصلضرب دو عدد را در نظر میگیریم. در این الگوریتم هر کدام از"n"  درایه از"x"  در"n" درایه"y"  ضرب می شود . واضح است که زمان اجرای این الگوریتم از مرتبهی formula_66 است .
همان طور که گفتیم در این بخش برای بهینه کردن مسأله ،الگوریتمهای دیگری معرفی کنیم. برای به دست آوردنحاصلضرب ، از روش تقسیم و حل استفاده میکنیم. مطابق زیر هر عدد"n"  رقمی را به دو بخش "" رقمی تقسیم میکنیم:
formula_67
formula_68
حاصلضرب"x"  و"y"  را میتوان به صورت زیر بازنویسی کرد:
formula_69
میتوان ابتدا هر کدام از حاصلضربهای سمت راست تساوی بالا را به صورت بازگشتی میتوان انجام داد و سپس بااستفاده از نتایج به دست آمده حاصلضرب مورد نظر را به دست آورد.
حال اگر تغییر متغیرهای زیر را در نظر بگیرید:
("p" = "a" · "c , p" = "b" · "d , p" = ("a" + "b")("c" + "d"حاصلضرب"x" · "y"  را به صورت زیر میتوان بازنویسی کرد:
formula_70
با نوشتن معادله بازگشتی روشن میشود که این روش نسبت به روش قبل زمان اجرای کمتری دارد. در مرحلهی تقسیم مسأله به سه زیر مسأله، هر کدام به اندازهی ("T"("" تقسیم میکنیم و هزینهی مرحلهی ادغام (Θ("n" است، پس معادلهبازگشتی آن به صورت زیر است:
formula_71
اگر با الگوریتم متداول یک ماتریس"n" × "n"  مانند"x"  را در یک ماتریس"n" × "n"  مانند"y"  ضرب کنیم هزینه ضرب از مرتبهformula_73 است .
برای این کار به روش تقسیم، هر ماتریس"n" × "n"  را به چهار زیرماتریس به شکل زیر تقسیم میکنیم:
formula_74
با استفاده از تغییر متغیرهای زیر میتوانیم الگوریتم را بازنویسی کنیم:
"T"("n") = ۸"T"("") + "θ"("n") =⇒ "T"("n") = "θ"("n")
الگوریتم حاصلضرب دو ماتریس به همان روش عادی یعنی استفاده از دو حلقه یfor را در نظر میگیریم و میدانیم که هزینه ی آن formula_73است، اما این روش مرتبه را کاهش نمیدهد پس به دلیل آن که میخواهیم الگوریتم را بهینهترکنیم ، برای این کار از چند متغیر جدید استفاده میکنیم.
formula_76
formula_77
معادله ی بازگشتی به صورت زیر میشود:
"T"("n") = ۷"T"("") + Θ("n")       ⇒      "T"("n") = Θ("n"۲) واضح است که جواب این معادله از مرتبه زمانی "T"("n") = ۷"T"("") + Θ("n")     است.
میخواهیم در یک آرایه مرتب ، عدد خاصی را بیابیم. اولین روش آن است که تمام آرایه را بپیماییم که از مرتبه"n" است. حال میخواهیم روشی را معرفی کنیم که بتواند با زمان کمتری این کار را انجام دهد.
ورودی: آرایهی مرتب("A" = ⟨"a1,a2...,an" و کلید"key"
خروجی: اندیس"i" ، به طوری که"A"["i"] = "key" . درصورتی که هیچ"i" ای یافت نشد 1− برگرداند.
میخواهیم در یک آرایه مرتب ، کلید خاصی را بیابیم. اولین روش آن است که تمام آرایه را بپیماییم که از مرتبه"n" است. در الگوریتمی که در ادامه توضیح داده شده است این کار را با مرتبه زمانی کمتری انجام می دهد. از روش تقسیم استفاده میکنیم یعنی آرایه را به دو قسمت تقسیم میکنیم و هرکدام را جداگانه در جستوجوی دودویی قرارمیدهیم تاجایی که به جواب برسیم.
در الگوریتم بعدی جستوجوی دودویی به صورت غیربازگشتی ارایه شده است.