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

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;
}

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

Answer 1

由于函数 g 的复杂性取决于参数 k（对数），因此在从函数 f 调用它时必须考虑它。如果 g 的最坏情况操作具有恒定的时间复杂度，那么您可能不需要明确考虑它。

在您的情况下， f 的复杂度为 O(n ² ) & g 的复杂度为 O(lg(n))，从而产生 O(n ² lg(n))的整体复杂度