下面程序的时间复杂度为：

Question

int fib(int x){
if(x<2)

return 1;

return x乘x乘fib(x-1) 
}

该程序的时间复杂度为多少？

Answer 1

大概是这样(对自己的数学水平比较没信心)n×n×((n-1)×(n-1))×((n-2)×(n-2))...×2×2×1=n!×n!=n!^2n每增加1,需要增加的操作是固定的,所以是线性相关,算法里线性相关O=kN的复杂度,k基本都可以忽略,所以时间复杂度我们认为他是O(n)就可以了...