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)，但我也对一般情况感兴趣（例如 if f(n)=O(n)）。

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

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

标签： recursiontime-complexitybig-opartitioning

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：

同样的结果，qed