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))。