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

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

فرمول

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

${\displaystyle T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x))\qquad {\text{for }}x\geq x_{0}.}$

که در آن:

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

رفتار حدی T(x) به صورت زیر و به ازای مقداری از p که ${\displaystyle \sum _{i=1}^{k}a_{i}b_{i}^{p}=1}$ بدست می آید:

${\displaystyle 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.