递归伪代码的时间复杂度

伪代码的时间复杂度函数是什么？递归伪代码的时间复杂度

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

2013-03-02 fean

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

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

所以它是O(fib N)。

2013-03-02 03:55:06

随着k增加，黄金比率的呼叫数量增加（渐近），但它不是斐波那契数列。从0开始的对n的调用次数为： ,1,1,3,5,9,15。同样，函数k（k）是k： - > Fib（k）。如前所述，所有的说明都表明，复杂性仍然是O（Fib（n））。

2013-03-02 04:58:33

可以请你告诉我乘法二元函数是在FIBO系列加（+），如步骤（*） - > FIB（K-1）+ FIB（K-2） – fean 2013-03-05 03:35:56

@fean：我没有关注你的问题。你能扩展吗？ – 2013-03-05 05:23:14

当它们位于两个相同递归函数的中间时，例如“fib（..）*/+ fib（..）”，在*和+之间是否有区别，如果是，那么在我的代码中有一个*运算符而不是+这不像斐波那契系列。 – fean 2013-03-16 03:17:33

我认为这个代码的时间复杂度为为O（n！），因为呼叫数乘以每个ķ增量（这是非常非常糟糕）。

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

int what(int k) { return 0; }

2013-03-02 08:20:21 PSIAlt

回答