performance - 递归伪代码的时间复杂度

Question

伪代码的时间复杂度函数是多少？

int what(int k){
   if(k==0 || k==1) 
      return k;
   else 
      return what(k-1)*what(k-2);
}

Answer 1

虽然随着 k 的增加，调用次数在黄金比例下（渐近地）增加，但它不是斐波那契数列。从 0 开始对 n 的 what() 调用次数为：1、1、3、5、9、15。同样，函数 what(k) 为 k：-> Fib(k)。

这一切都澄清了，复杂性仍然是 O(Fib(n))，如前所述。

Answer 2

我认为这段代码的时间复杂度是O(n!)，因为调用次数乘以每个k增量（这是非常非常糟糕的）。

（笑话）但我有好消息！这段代码可以简化为O(1)，因为它总是返回 0！

int what(int k) { return 0; }

Answer 3

该函数不计算斐波那契数列，但调用次数是斐波那契数列。

由于该函数在内部不做任何工作，因此时间复杂度与调用次数相同。

所以它是O(fib N)。