fabonacci函数时间复杂度

斐波那契数列是一个经典的数学问题，其递推公式为：F(n) = F(n-1) + F(n-2)，其中F(0) = 0，F(1) = 1。这个问题可以用递归、循环等方式求解。

对于递归实现的斐波那契数列，时间复杂度为O(2^n)，因为每次计算F(n)时需要计算F(n-1)和F(n-2)，而计算F(n-1)和F(n-2)又各需要计算一次F(n-2)和F(n-3)，如此递归下去，会有很多重复计算。

对于循环实现的斐波那契数列，时间复杂度为O(n)，因为只需要计算一遍F(n)就可以得到结果。具体实现方式可以使用两个变量分别记录F(n-1)和F(n-2)，然后不断更新它们的值即可。

总之，在实际应用中，我们应该尽量避免使用递归方式实现斐波那契数列，而是采用循环方式实现，以获得更好的时间复杂度。