计算划分问题的大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。

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

Calculate big O complexity of partitioning problem

recursion

big-o

partitioning

time-complexity