algorithm - 当等式右侧有多个循环函数调用时，求解循环关系的方法是什么？

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