计算分区问题的大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)。我不能应用Master定理，因为子问题的大小不一样。

如何计算这种递归的复杂性？

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。