寻找线性递归（递归算法）

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 函数的值，一切都已完成，结果已准备好返回。

另外，循环关系的证明来自你的分析。如果用组合数学中的一些计数原理，最后的结果就可以证明了。

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

寻找线性递归（递归算法）

Finding the linear recurrence (of a recursive algorithm)

algorithm

complexity-theory

time-complexity