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

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

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

在你的例子中，f 的复杂度是 O(n²) & g 的复杂度是 O(lg(n))，产生 O(n² LG(n))