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

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

فرمول

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

$T(x)=g(x)+\sum _{i=1}^k{a}_{i}T(b_{i}x+h_i(x))\text{for }x\ge x_0.$

که در آن:

• شرایط اولیه لازم قید شده است.
• $a_i$ و $b_i$ به ازای تمام مقادیر i ثابت هستند.
• $a_i>0$ و $0<b_i<1$ به ازای تمام مقادیر i
• $|g(x)|\in O(x^c)$ که در آن c ثابت است.
• $|h_i(x)|\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 \mathrm{\Theta }\left(x^p(1+\underset{1}{\overset{x}{\int }}\frac{g(u)}{u^{p+1}}du)\right)$

منابع

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