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

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!^2

n每增加1,需要增加的操作是固定的,所以是线性相关,算法里线性相关O=kN的复杂度,k基本都可以忽略,所以时间复杂度我们认为他是O(n)就可以了...