斐波那契数列算法时间复杂度

斐波那契数列是一个经典的数列，定义如下：第一个和第二个数为1，从第三个数开始，每个数都是前两个数的和。即：1, 1, 2, 3, 5, 8, 13, 21, ...

斐波那契数列算法的时间复杂度取决于具体的实现方式。常见的两种实现方式是递归和迭代。

1. 递归实现：
递归实现是最直观的方式，但效率较低。递归的思路是将问题分解为两个子问题，然后再将子问题分解为更小的子问题，直到达到基本情况。递归实现的时间复杂度可以表示为O(2^n)，其中n是斐波那契数列的索引。

2. 迭代实现：
迭代实现是一种更高效的方式。通过使用循环来计算斐波那契数列中的每个数，避免了重复计算。迭代实现的时间复杂度为O(n)，其中n是斐波那契数列的索引。

综上所述，斐波那契数列算法的时间复杂度取决于具体的实现方式，递归实现的时间复杂度为O(2^n)，而迭代实现的时间复杂度为O(n)。