为什么斐波那契数列算法复杂度（斐波那契数列巧妙推导）

斐波那契数列算法的复杂度为O(2^n)，其中n是要计算的斐波那契数的索引。这是因为斐波那契数列算法是通过递归来计算的，每次递归调用都会产生两个子问题，因此时间复杂度会呈指数级增长。

通过斐波那契数列的递归计算方式，会有很多重复计算的子问题，所以可以通过使用动态规划或者记忆化的方法来优化算法的性能，将时间复杂度降为O(n)。

斐波那契数：斐波那契数列指的是1、1、2、3、5、8、13、21、······这样一个数列，我们可以发现它后面的一个数是前两个数之和。而在这个数列中的数就被称为斐波那契数。

时间复杂度：时间复杂度实际就是一个函数，该函数计算的是执行基本操作的次数。

时间复杂度的O渐进表示：算法语句总的执行次数是关于问题规模N的某个函数，记为f(N)，N称为问题的规模。语句总的执行次数记为T(N)，当N不断变化时，算法执行次数T(N)的增长速率和f(N)的增长速率相同。则有T(N) =O(f(N))，称O(f(N))为时间复杂度的O渐进表示法。

空间复杂度：类似于算法的时间复杂度，它是算法所需存储空间的度量，记作S(n)=O(f(n))。