算法递归公式计算

Question

我有以下递归:

T(n) = T(2*n / 3) + T(n / 3) + O(n log n)

我需要知道确切的方程式，我知道大师定理对我没有帮助。

请告诉我一般如何进行此类递归。我需要复杂性并了解如何解决此类问题。

提前致谢。

Answer 1

主定理的推广是 Akra-Bazzi method .

假设你的 O(n log n) 实际上是 Θ(n log n)，我们有 g(x)=x log x, a_i=1 for i=1 and i= 2、b₁=2/3，b₂=1/3。则当p=1时b₁^p+b₂^p=1，g(u)/u< sup>p+1=(log u)/u有积分(log²u)/2，T(x)为Θ(x log²x)。