递归伪码的时间复杂度

Question

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

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

Answer 1

虽然调用的数量随着k的增加以黄金比率(渐近地)增加，但它不是Fibonacci序列。对于从0开始的n，对what()的调用次数是: 1，1，3，5，9，15。还有，函数what(k) is k：-> Fib(k)。

所有这些都清楚了，复杂度仍然是O(Fib(n))，如前所述。

Answer 2

该函数不计算Fibonacci序列，但调用次数是Fibonacci序列。

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

所以它就是O(fib N)。

Answer 3

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

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

int what(int k) { return 0; }