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

斐波那契数列是一个递归定义的数列，第n个数为前两个数之和，即F(n) = F(n-1) + F(n-2)，其中F(0)=0，F(1)=1。常见的计算斐波那契数列的方法有递归、循环和矩阵快速幂等。

递归方法的时间复杂度可以通过递归树来计算。每个递归函数调用会产生两个子问题，递归树的高度为n，因此递归方法的时间复杂度为O(2^n)。但是由于递归过程中存在很多重复计算，可以通过记忆化搜索（即备忘录方法）来避免重复计算，从而将时间复杂度降为O(n)。

循环方法的时间复杂度为O(n)，因为需要计算n次。

矩阵快速幂方法的时间复杂度为O(logn)，因为需要进行logn次矩阵乘法。