algorithm - 寻找线性递归(递归算法)

Question

我需要帮助来找出递归算法的复杂性；我知道为了解决这个问题，我必须找到线性递归，然后应用主定理。据我所知，当只考虑一个参数时，找到重复会很简单；
在这种情况下，有两个参数 (i, j)。考虑下面调用 (A,1,n) 的函数:

   integer stuff(integer [] A, integer i, integer j){
           if i ≥ j then return i – j 
           integer h ← 0
           for integer k ← 1 to floor((j – i + 1)/3) do {
              h ← h + 1
           }
           return stuff(A, i , i + h) + stuff(A, j – h, j) – stuff(A, i + h + 1, j – h − 1)
   }

假设各种事情，我猜的关系是:

T(1) = k  
T(n) = T(n/3) + T(n/3) + T(n/3) + 1/3*n = 3*T(n/3) + 1/3*n

我假设，因为看起来函数被调用超过 3 个部分，其中每个部分是 n 的三分之一；为 h = O(n/3)

First call: h+i-i = h ~ n/3   
Second call: j-(j-h) = h ~ n/3   
Third call: j-h-1-(i+h) = j-i-2h ~ n/3 (which I only assumed)

尽管我可以尝试猜测其中的关系并从中理解它，但我不知道如何正式证明它。
如果我的猜测是正确的，你是如何得出这个结论的？如果不是，我错过了什么？

抱歉问题太长了，提前致谢

Answer 1

当您在for 中return 时，这意味着函数将始终以恒定的复杂度完成!因为所有时间都进入 for 循环，它返回函数的值，一切都完成了，结果准备好返回。

此外，循环关系的证据来自您的分析。如果你使用一些组合学中的计数原理，最终的结果将被证明。

此外，如果你更正伪代码并将return放在函数的末尾，复杂度是T(n) = 3T(n/3) +\Theta(n )(如您分析的那样)。现在，根据主定理，您可以说 T(n) = n log(n))。