具有多个函数调用的递归函数的大 O？

Question

我无法确定此递归函数的最坏情况时间复杂度：

long f(int n) {
  if(n <= 0) return 1;
  else {
    return f(n / 2) + f(n / 2) + f(n / 2);
  }
}

我知道如果你只返回 f(n / 2) 一次，那就是 O(log n)。所以我想知道使用它三次、四次、五次等是否会影响函数的大 O。谢谢！

Answer 1

乘以常数从不影响复杂度。当然，执行时间大约增加了三倍，但问题是时间如何相对于 n 的值增加，而不是时钟显示的内容。

请注意，这很容易应用，因为您使用相同的值调用相同的函数；这可以可靠地替换为

return 3 * f(n/2)

如果您有三个 不同的 电话，例如

return f(n/2) + f(int(sqrt(n)) + f(n-1)

...那么你必须计算每个的复杂性并只考虑最复杂的。这个功能并不难；但是，对于更复杂的函数，例如 Collatz 序列，考虑所有二阶和三阶复杂性，您会遇到更多困难。调用间接递归函数也会遇到更多麻烦，例如

long f(int n);

long g(int n) {
  if(n <= 2) return 1;
  else {
    return f(n*n mod 10) + g(n-2);
  }
}

long f(int n) {
  if(n <= 0) return 1;
  else {
    return f(n / 2) + g(n / 2);
  }
}

底线：你的问题很简单，但要注意后续问题。

具有多个函数调用的递归函数的大 O？

Big O of recursive functions with multiple function calls?

recursion

big-o

time-complexity