小编Dat*_*den的帖子

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

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

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()？