روش اکرا-بازی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم رایانه اکرا-بازی روشی است برای بررسی پیچیدگی محاسباتی یک رابطه ی بازگشتی که در طراحی الگوریتم ظاهر می شود که تعمیمی است بر قضیه اصلی واکاوی الگوریتم‌ها.

فرمول[ویرایش]

این روش به رابطه ی زیر اعمال می شود:

که در آن:

  • شرایط اولیه لازم قید شده است.
  • و به ازای تمام مقادیر i ثابت هستند.
  • و به ازای تمام مقادیر i
  • که در آن c ثابت است.
  • به ازای تمام مقادیر i
  • یک ثابت است.

رفتار حدی T(x) به صورت زیر و به ازای مقداری از p که بدست می آید:

منابع[ویرایش]

  • Mohamad Akra, Louay Bazzi: On the solution of linear recurrence equations. Computational Optimization and Applications 10(2):195–210, 1998.