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

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

فرمول

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

$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.