函数调用另一个函数的时间复杂度？

Question

我知道如何找到几乎所有选项（简单函数、带循环的函数等）的时间复杂度，但我不知道如何确定调用函数的时间复杂度另一个函数，特别是如果调用函数在循环内。

我写了一些函数，用作示例。

int g(int k) {
  int i=0;

  while(k>0) {
    i += k;
    k= k/2;
  }

  return i;
}

int f(int n) {
  int m = 0;

  for (int i=0; i<n; ++i) {
    for (int j=i; j<n; ++j) {
      m += g(j);
    }
  }

  return m;
}

我想不通：我是否必须考虑函数g()的时间复杂度，如果我必须如何在函数f()中计算它？或者我只是忽略函数 g() 并只包含函数 f() 中的函数调用？

Answer 1

您必须考虑 f 中 g 的复杂性。

g 具有 O(log(n)) 复杂性。

所以 f 的复杂性是这些复杂性 log(j) 的总和。

最坏的情况是O(n²log(n))。

Answer 2

因为，函数 g 的复杂度取决于参数 k（对数），您在从函数 f 调用它时必须考虑它。万一，如果g的最坏情况操作的时间复杂度是常量，那么你可能不需要明确考虑。

在你的例子中，f 的复杂度是 O(n²) & g 的复杂度是 O(lg(n))，产生 O(n[=14) 的整体复杂度=]2lg(n))

Answer 3

为了找出f的复杂度，只需将g的代码内联到f中，然后将其视为一个完整的函数。调用本身是O(1)，因此对复杂度没有影响，就好像g里面的代码是在调用g的地方执行的。

这在某些情况下是不正确的，例如，如果您按值传递一个大小为 n 的数组作为函数的参数：在这种情况下，数组副本本身将为 O(n)，因此调用会对复杂性产生一些影响。

Answer 4

这在直觉上是 n²log(n)，但更准确地说，您得到以下证明：

函数调用另一个函数的时间复杂度？

Time complexity of function calling another function?

c++

big-o

time-complexity

asymptotic-complexity