求解递归关系的方法是什么当方程右边有不止一个递归函数调用时

Question

我试图分析函数调用PEL(A[1..n])的复杂性，其中n是3的某个幂，PEL由以下算法定义:

function PEL(A[m..n]){
  if(n - m <= 1) return 1;
  else { 
    p := [(n - m + 1)/3];
    MAKE(A[m..n]);
    PEL(A[m..n + p - 1]); PEL(A[m + p .. m + 3p - 1]);
  }
}

MAKE(A[m..n])的复杂度为theta((n-m)log(n-m))。

从我目前收集到的，我们正在处理以下递归关系:

C(N) = C(N/3) + C(2*N/3) + theta( (n-m)log(n-m) )

,

C(1) = C(2) = 1

我明白我们需要在这里应用主定理，但是在主定理中我们有这样的递归关系:

C(N) = a * C(N/b) + f(n)

我不知道如何在我的递归关系中摆脱对C()的第二次循环调用，那么我该怎么做呢?我不知道如何推导a和b的值。

Answer 1

正如所有评论者所说，我需要使用Akra-Bazzi定理。

C(1) = 1
C(2) = 1
For N > 2 we need to first find 'p' from the following equation : 
(1/3)^p + (2/3)^p = 1. It is obvious that p = 1.
Next we need to solve N^p * ( 1 + I[1,N](log(u)/u) ) with p = 1
I[1,N](x) denotes the integral of x, from 1 to N.
also I wrote log(u)/u instead of (u - 1)log(u-1)/u^2
since I((u-1)log(u-1)/u^2) looks like a monster.
I[1,N](log(u)/u) gives log^2(N)/2 so the end result is N + N*(log^2(N)/2).
All in all, the running time = theta( N + N*(log^2(N)/2) ).