k元递归函数的查找时间复杂度

Question

考虑以下二进制递归斐波纳西程序：

Algorithm binaryFib(k)  //k is assumed to be non-negative integer
   if (k <= 1)
      return k
   else
      return binaryFib(k-1) + binaryFib(k-2)
end binaryFib

以上的重复关系是：

T（n）= T（n-1）+ T（n-2）

相同的运行时复杂度为O（2 ^ n），如下面的n = 8所示：

但是，如果您查看树的底部，例如，取n = 3，它将不会在每个级别上运行2 ^ n次：

Q1。这个事实对时间复杂度没有影响，还是时间复杂度O（2 ^ n）忽略了这个事实？

Q2。我想我可以通过以下递归关系消除上述事实来重新表达Q1：T（n）= 2 * T（n-1）。这个递归关系是否仍然具有相同的O（2 ^ n）时间复杂度？

Q3。最后我要概括一下：递归关系T（n）= k * T（n-1）是否具有O（k ^ n）时间复杂度？

Answer 1

您说对了，这将不会运行2 ⁿ