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

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

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

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

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

T(x)=g(x) + \sum_{i=1}^k a_i T(b_i x + h_i(x))\qquad \text{for }x \geq x_0.

که در آن:

  • شرایط اولیه لازم قید شده است.
  • a_i و b_i به ازای تمام مقادیر i ثابت هستند.
  • a_i> 0 و 0 <b_i <1 به ازای تمام مقادیر i
  • \left|g(x)\right| \in O(x^c) که در آن c ثابت است.
  • \left| h_i(x) \right| \in O\left(\frac{x}{(\log x)^2}\right) به ازای تمام مقادیر i
  • x_0 یک ثابت است.

رفتار حدی T(x) به صورت زیر و به ازای مقداری از p که \sum_{i=1}^k a_i b_i^p = 1 بدست می آید:

T(x) \in \Theta \left( x^p\left( 1+\int_1^x \frac{g(u)}{u^{p+1}}du \right)\right)

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

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