c++ - 两个输入的函数的 T(n) 运行时间

Question

您如何找到具有两个输入的函数的 T(n) 运行时间（不是大 O 运行时间）？你只考虑输入你的'n'吗？

int h(int a, int b) {
  if (a > 0) {
    return h(a-1, a+b);
  } 
  else {
    return 0;
  }
}

score 3 · Accepted Answer

在这种情况下，我们只需要考虑a，因为该算法的长度不依赖于 b。

换句话说，由于我们可以为 b 传递 20000 或 -2 并且丝毫不会影响我们的时间（忽略添加的实际时间a+b），我们不应该在计算中考虑 b。

在更一般的情况下，如果输入确实取决于a并且b我们将在时间复杂度函数中简单地考虑这一点。换句话说，它T(a, b)不仅仅是T(a).

score 0 · Accepted Answer

鉴于对于每个 (a,b) 对，函数值都为零 - 递归将始终在 else 分支中结束 - 编译器可能足够聪明，可以有效地减少代码以对整个主体“返回 0”并留下所有 if/else 和递归的东西，导致 O(1) 复杂性和相应的运行时间。

score 0 · Accepted Answer

由于此函数仅在 a 上重复，并且 a 在每一步中都减少 1，因此它会给出线性复杂度。所以答案是 T(a)。

3 回答 3