algorithm - 具有嵌套迭代函数的递归算法的时间复杂度？

Question

一)

void f(n){
  if(n<=1) return;
    else{
      g(n); //g(n) is O(N^2).
      f(n/2);
      f(n/2);
    } 
}

二)

void f(n){
  if(n<=1) return;
    else{
      g(n); //g(n) is O(N).
      f(n-1);
      f(n-1);
    } 
}

c)

void f(n){
  if(n<=1) return;
    else{
      g(n); //g(n) is O(N^2).
      f(n-1);
      f(n-1);
    } 
}

如何计算上述两个代码片段的 O(n) 复杂度？

a) 我得到了 O(n^2) 的答案，因为每个 f(n) 递归地调用自己两次。由于树的深度是 LogN (n/2)，整体复杂度是 O(n^2)，我是否忽略 g(n) 方法，因为它也是 N^2？

b) 由于树的深度为N，每个f(n)递归调用自己两次。又因为每一层都需要执行N次g(n)操作，所以我得到的答案是O(N.2^(N))。

c) 与 b) 相同，但 g(n) 执行 N^2 次 - 因此 O(N^2.2^(N))。

这是正确的吗？

Answer 1

a) 递归方程如下。

如果你展开递归，我们有:

所以我们要计算最后一个等于:

由于上式的最后一部分是一个几何级数，我们有:

所以递归是 .

b) 方法同上。

等于:

所以答案是

c) 第三部分可以用同样的技巧解决。

附言:感谢 Alexandre Dupriez 的评论。

PS:要优雅简化总结，请阅读 Alexandre 的评论。