الگوریتم های بازگشتی و بررسی پیچیدگی آنها

این نوشته یک بازگردان فارسی از Computational Complexity Part Two منتشر شده توسط misof در وبسایت topcoder.com است. در ترجمه مطلب تلاش شده تا بهترین واژه ها جایگزین شود و نوشتار به گونه ای باقی بماند که امانت ترجمه حفظ شده و همزمان برای خواننده قابل فهم و درک باشد هرچند در طول متن ممکن است مواردی چندان واضح نباشد که خب به علت پیچیدگی نسبی برای کسی که از قبل با مباحث مطرح شده آشنایی ندارد در خود مقاله اصلی شاید بعضی بخش ها نیاز به خوانش چند باره داشته باشند. موضوع بحث بررسی پیچیدگی الگوریتم های بازگشتی در علوم کامپیوتر است و بدین منظور مراجعاتی به دانش ریاضی نیز صورت گرفته. در صورتی که پیشنهادی برای بهتر شدن ترجمه دارید از بخش نظرات با من در میان بگذارید.
بخش هایی که داخل [ ] آمده اند نوشته مترجم برای شفاف سازی منظور یا ارائه توضیحات مربوط به بحث در آن مقطع است.

اصل مقاله را میتوانید از طریق لینک زیر مطالعه بفرمایید:

در این بخش مقاله[ مقاله در دو بخش نوشته شده که بخش اول آن مربوط به معرفی مفهوم پیچیدگی الگوریتم ها و مبانی آنهاست که از اینجا میتوانید بخوانید] ما روی تخمین پیچیدگی زمانی برنامه های بازگشتی توجه می کنیم. طبیعتا این کار منجر به یافتن ضریب رشد[order of growth در اینجا ضریب رشد ترجمه شده] برای جواب ها یک معادله بازگشتی خواهد شد. اگر دقیقا نمی دانید که جواب بازگشتی چیست ،نگران نباشید، آن را در مکان درست و در زمان درست توضیح خواهیم داد، اما در ابتدا ما یک کیس ساده تر را بررسی میکنیم- برنامه های بدون بازگشت.

حلقه های تو در تو

در ابتدا اجازه دهید برنامه های ساده که توابع را صدا نمیزنند بررسی کنیم. قانون کاربردی برای پیدا کردن پیچیدگی الگوریتم چنین برنامه ای اینچنین است :

1. تخمین بزنید که هر حلقه حداکثر چند بار میتواند اجرا شود.
2. جواب را برای حلقه هایی که بعد از یکدیگر می آیند جمع بزنید.
3. جواب را برای حلقه های تو در تو داخل کد در هم ضرب کنید. [برای مثال اگر یک حلقه با n بار تکرار دارید که داخل آن حلقه دیگری با 2n بار تکرار وجود دارد باید آن ها را در هم ضرب کنید و به n*2n=2n^2 برسید.]

مثال 1: تخمین پیچیدگی زمانی یک تکه کد تصادفی :

int result = 0; //  1
for (int i = 0; i < N; i++) //  2
  for (int j = i; j < N; j++) { //  3
    for (int k = 0; k < M; k++) { //  4
      int x = 0; //  5
      while (x < N) {
        result++;
        x += 3;
      } //  6
    } //  7
    for (int k = 0; k < 2 * M; k++) //  8
      if (k % 7 == 4) result++; //  9
  } // 10

پیچیدگی زمانی حلقه While در خط ششم واضحا از مرتبه n ام ( O(n) ) است( از آنجایی که قطعا بیشتر از N/3 +1 بار اجرا نخواهد شد.[ توضیحات مترجم : چون پرش ها در متغیر iterator یعنی x در هر مرحله 3 واحد است-خط هشت ] )

حالا به حلقه های for در خطوط 4تا7 دقت کنید. واضح است متغیر k ، به تعداد M دفعه افزایش پیدا میکند و هر دفعه حلقه while خط 6 اجرا می شود بنابراین کل پیچیدگی خطوط 4 تا 7 از مرتبه O(M*N) است.

پیچیدگی زمانی حلقه for خطوط 8تا9 از مرتبه O(M) است; بنابراین پیچیدگی زمانی خطوط 4 تا 9 از مرتبه MN+M یعنی O(MN) است.[ با فرض اینکه N متغیر اصلی مسئله است خط (شیبدار صعودی) همواره رشد بیشتری نسبت به ثابت ( که البته خود ثابت هم خط افقی است) دارد و در مقادیر بزرگ M قطعا MN غالب خواهد بود].

بخش داخلی از مرتبه O(N^2) بار اجرا خواهد شد-یک بار برای هر ترکیب i و j.(توجه کنید کل در کل N(N+1)/2 حالت برای i و j وجود دارد ولی بدون در نظر گرفتن ثابت ها و حذف جملات با رشد کمتر در بینهایت ، جواب در نهایت از مرتبه N^2 است.)

از موارد بالا میتوان نتیجه گرفت که پیچیدگی زمانی الگوریتم بالا از مرتبه MN*N^2 یعنی O(MN^3) است.

از اینجا به بعد تصور میکنیم که خواننده توانایی این را دارد که time complexity الگوریتم های ساده را به روشی که در بالا نشان داده شد تقریب بزند. حالا برنامه هایی با بازگشت را در نظر میگیرم(هنگامی که یک تابع خودش را گاها با پارامتر های مختلف صدا بزند) و تلاش می کنیم که تاثیر این بازگشت ها را روی پیچیدگی زمانی این توابع بررسی کنیم.

استفاده از بازگشت برای ایجاد اشیاء ترکیبی

یکی از کاربرد های بازگشت پیاده سازی الگوریتم های backtracking به منظور تولید تمام جواب های ممکن برای یک مسئله است. ایده کلی ایجاد تمام پاسخ های ممکن بصورت فزاینده است و در نهایت بازگشت به عقب پیدا کردن یک راه دیگر هنگامی که تمامی جواب های یک شاخه ناموفق هستند.

این رویکرد کاملا همه جانبه نیست و مسائلی وجود دارند که غیر ممکن است که همه جواب ها را بصورت افزایشی تولید کرد ، هر چند خیلی اتفاق می افتد که مجموعه تمام جواب های قابل قبول یک مسئله با یک مجموعه اشیاء ترکیبی یک ریخت متناسب است. اغلب آن مجموعه ، مجموعه همه جایگشت ها(با طول مشخص)است . اما سایر اشیاء(ترکیب ها[توضیح مترجم: جایگشت ها ترکیباتی از یک سری اشیاء هستند که ترتیب در آنها اهمیت دارد. یعنی تغییر ترتیب قرار گیری اشیاء خود یک جایگشت جدید ایجاد می کند] ، اجزا و … ) نیز به گاها دیده می شود.

به عنوان نکته جانبی ، همواره میتوان تمام ترکیب صفر و یک را ایجاد کرد و تک تک آن ها را آزمود(یعنی بررسی کرد که آیا در مسئله صدق می کنند) و بهترین پاسخ را نگاه داشت. اگر ما بتوانیم برای بهترین جواب از بالا یک مرز پیدا کنیم آنگاه این روش محدود و متنهایست. هر چند این رویکرد اصلا سریع نیست. از این روش استفاده نکنید مگر اینکه هیچ روش دیگری وجود نداشته باشد.

مثال 2: یک الگوریتم نه چندان قوی برای برای ساختن تمام جایگشت های ارقام 0 تا n-1 :

vector permutation(N);
vector used(N, 0);

void
try (int which, int what) {
  // try taking the number “what” as the “which”-th element
  permutation[which] = what;
  used[what] = 1;

  if (which == N - 1)
    outputPermutation();
  else
    // try all possibilities for the next element
    for (int next = 0; next < N; next++)
      if (!used[next])
        try (which + 1, next);

  used[what] = 0;
}

int main() {
  // try all possibilities for the first element
  for (int first = 0; first < N; first++)
    try (0, first);
}

در این مثال یک کف نه چندان نزدیک برای پیچیدگی زمانی الگوریتم تعداد پاسخ های ممکن است.

الگوریتم های عقب روند [منظور همان الگوریتم های بازگشتی است.] معمولا برای حل کردن مسائل دشوار استفاده می شوند( برای مثال هنگامی که ما نمی دانیم که راه حلی که بطور قابل توجه بهینه تر باشد وجود دارد یا خیر؟

پاسخ های ممکن برای مسائل اینچنینی و در نتیجه پیچیدگی زمانی آنها معمولا رشد نمایی (یا حتی بدتر) دارند.

با روش تقسیم و حل [ ترجمه اصطلاح Divide and conquer در طراحی الگوریتم به معنی بخش بخش کردن مسئله و حل مستقل هر کدام از بخش ها و در نهایت پیوستن جواب هاست که تکنیکی رایج در حل مسائل است.]

از مثال قبلی این احساس به ما منتقل شد که بازگشت کند است و به ساخت برنامه های آهسته و کند می انجامد. دقیق برعکس است.بازگشت میتواند یک روش خیلی قدرتمند برای طراحی الگوریتم های کارآمد باشد. راه معمول برای ساخت برنامه های بازگشتی کارآمد و بهینه استفاده از الگوی "تفرقه اندازی و غلبه" است-تلاش میکنیم مسئله را به بخش های کوچکتر و مستقل تبدیل کنیم. هر بخش را بطور جداگانه حل می کنیم.در نهایت پاسخ ها در هر بخش را کنار هم قرار میدهیم تا به پاسخ مسئله برسیم. لزومی ندارد که اشاره کنیم "هر بخش را بطور جداگانه حل میکنیم" توسط بازگشت انجام می شود و کوچک کردن مداوم مسئله تا به یک بخش قابل حل برسیم توسط brute-force انجام می شود.[توضیح مترجم: تکنیک brute-force عملا معنی تلاش چندین و چند باره را می دهد که توسط حلقه ها انجام می شود.]

مثال 3: کد زیر الگوریتم مرتب سازی MergeSort را [در منابع فارسی به آن با نام مرتب سازی ادغامی نیز اشاره شده] در فرمت سودو کد نشان میدهد:

کد زیر الگوریتم مرتب سازی MergeSort را [در منابع فارسی به آن با نام مرتب سازی ادغامی نیز اشاره شده] در فرمت شبه کد نشان میدهد:

MergeSort(sequence S) {
  if (size of S <= 1) return S;
  split S into S_1 and S_2 of roughly the same size;
  MergeSort(S_1);
  MergeSort(S_2);
  combine sorted S_1 and sorted S_2 to obtain sorted S;
  return sorted S;
}

واضح است که زمان O(N) برای شکستن یک آرایه N عضوی به دو آرایه کافی است.( بسته به نحوه پیاده سازی اینکار حتی میتواند در زمان ثابت یعنی O(1) نیز انجام شود.) ادغام کردن دو آرایه مرتب شده کوچکتر میتواند در O(n)[در اینجا نویسنده از تتا استفاده کرده-به درستی هم استفاده کرده اما برای سادگی من اکثر نماد ها رو در ترجمه از همان Big-Oh استفاده میکنم که هم سر شما در نیاد برای محاسبات ریاضیش هم اینکه درستی مطلب هم دست نخورده باقی میمونه]

[ توضیح در مورد پاراگراف بالا : برای MergeSort کردن یک آرایه ما اون رو به دو آرایه کوچک تقسیم میکنیم بعد خود اون دو تا رو Mergesort میکنیم ( که البته چجوریش خودش مهمه ، ما هنوز روش دقیقی برای Mergesort نگفتیم به شما) و در نهایت اون دو آرایه مرتب شده رو ادغام میکنیم به جوری که حاصل نیز مرتب باشه. زمانی که دو تا آرایه روی هم N عنصر داشته باشن برای مرتب شدن طبق گفته نویسنده پیچیدگی زمانی ادغام این دو تا از مرتبه N هست. توجه کنید که صرفا کنار هم نمیزاریمشون بلکه عناصر هر کدوم باید نسبت به اون یکی هم در خروجی مرتب باشن برای همین O(1) نیست پیچیدگیش. چجوری ادغام دو آرایه مرتب و دلیل اینکه پیچیدگی مرتبه N داره در ادامه متن اومده. ]

آرایه خالی S رو در نظر بگیرید که ادغام شده S1 و S2 باشد. در هر لحظه عنصر بعدی که باید توی S قرار داده شود عنصر اول S1 یا عنصر اول S2 است. این دو عنصر را مقایسه کنید ، عنصر کوچکتر را در انتهای S قرار دهید و از آرایه کوچکتری که متعلق به آن است حذف کنید. اگر این کار را n-1 بار تکرار کنید در نهایت به آرایه کامل مرتب شده و ادغامی S1 و S2 یعنی S می رسید.

در نتیجه زمان کلی ادغام کردن یک آرایه با N عنصر از مرتبه O(n) است + زمانی صدا زدن تابع بازگشتی برای دو بخش مجزا.

[ توضیح مترجم : جمله بالا می گوید : برای اینکه یک سری اعداد با N عضو را مرتب سازی کنیم زمان کلی مصرف شده زمانی هست که ما این دو تا را خودشون رو اول مرتب کنیم + زمانی که این دو تای مرتب شده رو ادغام میکنیم(که در پاراگراف بالا فهمیدم از مرتبه N هست این یکی) ]

فرض کنید f(N) پیچیدگی زمانی باشد الگوریتم MergeSort باشد. توضیحات بالا ما را به این نتیجه میرساند :

که p(N) یک تابع خطیست که بیانگر زمان مصرف شده برای شکستن آرایه اصلی به دو آرایه و ادغام کردن آن دو آرایه زمانی که مرتب شده اند هست.

[توضیح مترجم : اینجا شاید یکم سخت بنظر برسه ولی خیلی پیچیده نیست. تابع f بیانگر زمان کلی مصرف شده توسط الگوریتم بر حسب سایز آرایه ای که میخوایم مرتب کنیم هست. حالا دقیقا همون توضیحات بالا آورده شده. یک f(N/2) داریم که بیانگر زمان مصرف شده برای sort کردن یکی از دو آرایه ای هست که که اون اول با شکستن آرایه N عضوی ساختیم. دوباره یک f(N/2) دیگه هم داریم که عین قبلی برای اون یکی آرایه شکسته شده هست. یدونه p(N) هم داریم که نشون دهنده زمان مصرفی برای این هست که 1: آرایه اصلی رو به دو تا آرایه N/2 عضوی بشکونیم. 2: بعد از اینکه آرایه های N/2 عضوی رو sort کردیم ، اینا رو با هم ادغام کنیم. چون نتیجه گرفتیم که هر دو تای این عمل ها از مرتبه N هستن پس قطعا جمعشون هم مرتبه N هست و در نهایت p باید خطی باشه]

دقت کنید این به تعبیر متداول یک معادله نیست. مانند مثال های بخش اول این مقاله علامت تساوی به معنی "از نظر asymptotic analysis برابر است با ..." است. معمولا توابع بسیاری هستند که در تساوی بالا صدق می کنند اما معمولا تمام آنها از نظر مرتبه رشد یکسان هستند- که این دقیقا همان چیزی هست که ما به دنبال آن هستیم. یا در حالت کلی تر میخواهیم یک مرز بالایی نزدیک برای تمامی جواب هایی که در معادله بالا صدق می کنند بیابیم.

در بخش های انتهایی این مقاله روش های متفاوتی را برای یافتن این "معادلات" بررسی میکنیم. قبل از آن نیاز داریم که کمی راجع به لگاریتم صحبت کنیم.

[توضیح مترجم : توابع لگاریتمی جز توابع نسبتا ساده ریاضی با تعاریف و قوانین سر راست هستند که در نظام آموزشی 6-3-3 ایران در کتاب های درسی پایه یازدهم آموخته می شوند. برای بررسی بیشتر میتوانید به این کتاب ها مراجع کنید.]

نکاتی راجع به لگاریتم

تا الان احتمالا یکی از این سوالات را از خودتان پرسیده اید : هنگامی که نویسنده میگوید پیچیدگی یک تابع از مرتبه مثلا O(N*Log(N)) است ، پایه لگاریتم چیست ؟ آیا در بعضی موارد بیان کردن پیچیدگی با لگاریتم پایه 2 بهتر نیست؟

پاسخ: پایه لگاریتم اصلا مهم نیست. تمام لگاریتم ها از نظر مرتبه رشد یکسان هستند. این به علت قانون زیر در لگاریتم هاست:

دقت کنید که اگر a و b را مثل بالا پایه های لگاریتم در نظر بگیریم لگاریتم a در پایه b (مخرج کسر) یک ثابت است.در نتیجه لگاریتم N در پایه a همواره ضریبی از لگاریتم N در پایه b خواهد بود.

برای دادن توضیحات بهتر و نوشتن عبارات ساده تر ما همواره از عبارت log(n) درون علامت big-Oh استفاده می کنیم ، چه بسا لگاریتم با پایه های مختلفی برای محاسبه مرز های تابع استفاده شده باشد.

در ضمن متاسفانه معنی log(N) در کشور های مختلف یکسان نیست و از کشور به کشور میتواند فرق کند.برای جلوگیری از ایجاد ابهام منظور من از log(N) در مبنای 10 است و منظورم از lg(N) لگاریتم N در مبنای 2 است و در بقیه موارد پایه ذکر می شود.

حالا چند تکنیک لگاریتمی به شما نشان میدهیم که در ادامه از آنها استفاده می کنیم.

با فرض اینکه a و b ثابت هایی بزرگتر از 1 باشند :

با دانستن قاعده بالا میتوانیم نتیجه زیر را بگیریم :

روش های حل معادلات بازگشتی:

روش اول :جانشینی

این روش را میتوانیم در یک جمله خلاصه کنیم: یک حد بالایی برای f حدس میزنیم و سپس حدس را با استقرا ثابت می کنیم:

برای مثال ثابت می کنیم که اگر f در معادله 1 صدق کند آنگاه f(N)=o(Nlog(N)).

از معادله 1 میدانیم برای بعضی از مقادیر c :

حالا ثابت می کنیم که اگر d را به اندازه کافی بزرگ انتخاب کنیم آنگاه برای تقریبا همه N ها داریم : f(N) <= d(n*lg(N)). اثبات را از حکم مسئله شروع می کنیم:

به عبارت دیگر حکم استقرا تا وقتی که d>c باشد برقرار خواهد بود. از آنجایی که d و c ثابت های دلخواه هستند ما میتوانیم این فرض را درست در نظر بگیریم.

تنها کاری که الان باید انجام دهیم ثابت کردن معادله برای یک مقدار اولیه N است. هنگامی که بخواهیم اینکار را بصورت ریاضیاتی/استقرایی انجام دهیم کار بسیار دشوار می شود اما ایده کلی این است که هر گاه d به اندازه کافی بزرگ نبود میتواند بزرگتر انتخاب شود تا مقادیر اولیه N را پوشش دهد.

روش دوم : درخت بازگشت

برای یک مبتدی روش قبلی خیلی کارآمد واقع نخواهد شد.برای اینکه از روش قبلی استفاده کنیم باید یک حدس نسبتا خوب بزنیم-و برای اینکه حدس خوب بزنیم نیاز به بینش/تجربه داریم. سوال این است که چگونه این بینش را به دست آوریم؟ اجازه دهید یک نگاه نزدیک تر به آنچه که وقتی میخواهیم الگوریتم های بازگشتی را آنالیز کنیم اتفاق می افتد داشته باشیم.(در حقیقت اتفاقاتی که هنگامی که یک برنامه بازگشتی را اجاره میکنیم رخ میدهد)

ما میتوانیم اجرای یک برنامه بازگشتی با یک ورودی مشخص را به وسیله یک درخت شاخه شاخه نشان دهیم.هر سر شاخه نشان دهنده یک نمونه از سوالی است که برنامه قصد حل کردنش را دارد.

یک راس دلخواه برای درخت در نظر بگیرید.اگر حل کردن سوال در آن راس نیازمند فراخوان کردن توابع بازگشتی است این راس خود شامل شاخه هایی هست که وظیفه حل کردن سوال برای بخش های کوچکتر را بصورت بازگشتی دارند و به همین ترتیب ...

بالاترین راس (راس خود درخت) ورودی اصلی ما است و برگ ها ( راس های پایین پایین) نشان دهنده مسائل ساده و کوچک هستند که میتوانیم آن ها را حل کنیم.

[توضیح مترجم: این بخش نوشته شاید کمی گنگ بنظر برسد در مثال های بعدی احتمالا منظور را متوجه می شوید]

مثال 4: درخت بازگشتی برای الگوریتم MergeSort روی یک آرایه 5عنصری به این شکل است:

درخت بازگشتی برای معادله بازگشتی متناظر با الگوریتم به شکل زیر است. اینبار عدد نوشته شده در هر خانه تعداد قدم های الگوریتم هست.[منظور از قدم در اینجا اعمال ساده از O(1) است مثل جمع، ضرب،دسترسی به خواندن و نوشتن در مموری و ...]

توجه داشته باشید که با روشی تقریبا مشابه میتوان درخت بازگشت را برای هر الگوریتم بازگشتی دلخواه رسم کرد. دوست قدیمی مان یعنی معادله (1) را به خاطر آورید. در اینجا میدانیم که ثابتی مثل C وجود دارد که تعداد عملیات های الگوریتم در هر راس از c در مقدار N در آن زمان بیشتر نمی شود. بنابراین درخت مثال زیر در حقیقت بدترین سناریو است:
مثال 5: درخت بدترین حالت برای معادله بازگشتی (1) :

حالا روش معمول در ترکیبیات این است که عناصر با ترتیبی غیر از ترتیبی که در آن قرار دارند جمع بزنیم. در مثال یک تراز دلخواه از درخت را در نظر بگیرید(مجموعه ای از رئوس که از راس اصلی به یک فاصله قرار دارند/رئوسی که در یک طبقه هستند). واضح است که مجموع رئوس این تراز/طبقه همیشه C*N میشود.

حالا سوال دوم:چه تعداد طبقه وجود دارد؟(چون جمع رئوس در هر طبقه برابر است و مساوی CN است پس با ضرب CN در تعداد طبقات جمع کل رئوس معلوم می شود). تعداد طبقات در درخت همیشه متناسب با کیس های بدیهی الگوریتم هست.[توضیح مترجم:کیس های بدیهی کیس هایی هستند که بازگشت در آنها متوقف می شود و الگوریتم میتواند بدون بازگشت خروجی بدهد. در مرج سورت مثلا کیس بدیهی ورودی با یک عنصر است که الگوریتم صرفا همان عنصر را بر می گرداند و نیازی به بازگشت ندارند]

میدانیم که اندازه مسئله در هر طبقه نصف می شود. بنابراین بعد از lg(n) [تکرار میکنم در مقاله برای لگاریتم در پایه دو از lg استفاده می شود] به کیس بدیهی T(1) میرسیم که از مرتبه 1 است. در نتیجه تعداد طبقات از مرتبه تتا log(N) است. [ اشاره شد که پایه لگاریتم در Asymptotic Analysis اهمیت ندارد. ]

با در نظر گرفتن دو جوابی که یافتیم یعنی هزینه در هر طبقه و تعداد طبقات به این نتیجه میرسیم که کار کل انجام شده از مرتبه N*log(N) است.

مثال 6: بیاید روش جدیدمان یعنی "درخت بازگشتی" را برای حل معادله بازگشتی زیر به کار ببریم:

درخت بازگشتی معادله فوق به شکل زیر خواهد بود:

بیاید جمع چند طبقه اول را محاسبه کنیم:

واضح است که هر چه در درخت به طبقات پایین تر می رویم مجموع کار انجام شده طبقه ای که در آن قرار داریم کاهش می یابد.سوال این است: سرعت کاهش آن چقدر است؟ هنگامی که یک طبقه پایین می رویم تعداد مسائلی که باید در طبقه جدید حل شود سه برابر می شود ولی در عوض اندازه آن مسائل تقسیم بر دو میشود، در نتیجه زمان حل آن مسئله تقسیم بر 8 می شود. [ چون در معادله زمان صرف شده برای بخش غیر بازگشتی از مرتبطه N^3 است ] در نتیجه زمان کل صرف شده برای طبقه پایین 3/8 طبقه بالاتر از خودش است.

با تفاسیر بالا زمان صرف شده در هر طبقه از درخت بالا یک دنباله هندسی تشکیل می دهد.[ دنباله های حسابی/هندسی در ریاضیات سال دهم دبیرستان مورد بحث واقع می شوند. دنباله هندسی دنباله ای است که هر جمله آن با ضرب جمله قبلی در عددی ثابت(قدر نسبت) به دست می آید. ]

بیاید تصور کنیم که دنباله بی نهایت جمله دارد ، آنگاه مجموع جملات آن می شود:

[ مجموع جملات دنباله هندسی با بینهایت جمله(مثبت) که قدر نسبت q<1 دارند هنگامی که دنباله با جمله a شروع شود در بینهایت به a/(1-q) میل خواهد کرد.]

میبینیم که در بدترین حالت یعنی بینهایت طبقه هم مجموع کار انجام شده از مرتبه تتا N^3 است.

نکته مهم از این مثال: اگر کار انجام شده در طبقات یک درخت بازگشتی دنباله هندسی نزولی تشکیل دهند کار کل انجام شده در درخت تقریبا هم مرتبه کار انجام شده در راس های پایین ترین طبقه است.

از این نکته میتوانیم یک به یک حقیقت جالب راجع به الگوریتم(فرضی) پشت این معادله پی ببریم: بازگشت زدن به الگوریتم در اینجا زمان زیادی مصرف نکرده است. بیشترین زمان در هر طبقه بجای بازگشت زدن به تابع ، محاسبه ورودی ها و پردازش خروجی تابع بر اساس بازگشت بوده.(در نتیجه اگر بخواهیم الگوریتم را بهینه تر کنیم باید این بخش را تغییر دهیم.)

مثال 7: اکنون بیاید با روش "درخت بازگشتی" معادله زیر را حل کنیم:

درخت بازگشتی چیزی شبیه تصویر زیر است:

مانند قبل کار انجام شده در چند طبقه اول را حساب می کنیم:

اینبار قضیه بر عکس است. هر چه به طبقات پایین تر می رویم انگار کار انجام شده در آن طبقه بیشتر می شود. هر طبقه که پایین می رویم تعداد مسائل برای حل شدن 5 برابر می شود ولی اندازه آنها 3 برابر که چون کار انجام شده مستقل از بازگشت برای هر مسئله از مرتبه Theta(N) است پس کار کل انجام شده در طبقه 5/3 برابر می شود.

مثل قبل میخواهیم کل کار در همه طبقات را محاسبه کنیم. اینبار مسئله خیلی آسان نیست زیرا اکثر کار انجام شده در طبقات پایینی اتفاق می افتد. باید تعداد طبقات را بدانیم.

در پایین ترین طبقه مسائل اندازه 1 دارند. میتوان مشاهده کرد که طبق الگوی درخت در طبقه k ام سایز مسائل N/3^k است. با قرار دادن این عبارت برابر 1 شماره طبق آخر بر حسب N برابر با k = log3(N) به دست می آید. یعنی تعداد طبقات لگاریتم N در پایه 3 است. دقت کنید در اینجا ما پایه لگاریتم را گفتیم زیرا برخلاف نتیجه کلی که در نماد می آید برای جمع کل کار در طبقه ها پایه لگاریتم اهمیت زیادی دارد.

درخت ما log3(N) طبقه دارد. با قرار دادن مشخصات در رابطه مجموع جملات دنباله بازگشتی با داشتن تعداد جملات که همان تعداد طبقات است و دانستن قدرنسبت یعنی 5/3، کل کار انجام شده در درخت برابر مضربی از N به توانlog3(5) است.
دوباره قصد داریم که کار انجام شده در هر طبقه را جمع بزنیم تا به کل کار الگوریتم برسیم. دوباره با رشد هندسی سر و کار داریم. اینبار بجای اینکه دقیق مجموع را حساب کنیم ، برعکسش را انجام میدهیم. اکنون یک دنباله هندسی نزولی داریم و در وضیعتی مشابه مثال قبلی هستیم. با استدلال مثل دفعه قبل به این نتیجه خواهیم رسید که جمع همه از نظر بزرگی رشد (یعنی بدون حساب ضرایب و جملات با رشد کوچک) برابر بزرگترین عنصر دنباله است.

قضیه اساسی

[ادامه مقاله در Top Coder مربوط به قضیه اساسی محاسبه مرتبه بزرگی است. چون این قضیه جای صحبت بیشتر و بررسی پیشرفته تر دارد سعی میکنم بعدا آنرا جداگانه و با راهنمای بهتر و کامل تر منتشر کنم.]