斐波那契算法时间复杂度和空间复杂度

斐波那契算法是一种递归算法，用于计算数列中每个位置的值，该数列从0和1开始，后续每一项都是前两项之和。其经典递归版本的时间复杂度是O(2^n)，因为每次递归都会生成两个新的子任务。随着n的增长，需要解决的问题数量呈指数级增加，效率非常低。

空间复杂度方面，由于递归会形成一个栈，对于每一次函数调用，都需要在栈上保存一些信息（如当前的状态）。对于经典的递归实现，空间复杂度也是O(n)，因为在最坏的情况下，递归深度达到n，栈就会有n层，每层存储的信息是一样的。

然而，有一种迭代而非递归的实现，称为"记忆化"或者"动态规划"，可以显著降低空间复杂度到O(1)。这种改进方法通过缓存已经计算过的值，避免了重复计算，但时间复杂度仍然是O(n)。