recursion - 计算划分问题的大O复杂度

Question

我的伪代码如下所示:

solve(n)
    for i:= 1 to n do
       process(i);
       solve(n-i);

其中process(n)是一个具有一定复杂性的函数f(n)。就我而言，f(n)=O(n^2)，但我也对一般情况感兴趣(例如，如果f(n)=O(n) )。

所以，我有T(n) = f(n) + ... + f(1) + T(n-1) + ... + T(1)。我无法应用主定理，因为子问题的大小不同。

如何计算此递归的复杂度？

Answer 1

小技巧 - 考虑solve(n-1):

solve(n)  :  T(n)   =  f(n) + f(n-1) + f(n-2) + ... + f(1) + T(n-1) + T(n-2) + ... + T(0)
solve(n-1):  T(n-1) =         f(n-1) + f(n-2) + ... + f(1) +          T(n-2) + ... + T(0)

从前者中减去后者:

重复展开:

求解 f(n) 的最后求和以获得复杂度。

例如对于f(n) = O(n):

---

替代方法 - 变量替换:

S(m) 是主定理的正确形式。

例如对于 f(n) = O(n) = O(log m)，使用情况 2 和 k = 0:

相同的结果，q.e.d。