斐波那契数列的时间复杂度
求解斐波那契数列F(n)={1,n=0,1F(n−1)+F(n−2),n>1F(n) =\left\{\begin{matrix}1,\quad n=0,1 \\F(n-1)+F(n-2),n>1\end{matrix}\right.F(n)={1,n=0,1F(n−1)+F(n−2),n>1有两种常用的算法：递归算法和非递归算法，根据不同算法分析它的时间复杂度。递归算法int
文章共8,008字 · 阅读需要大约27分钟
求解斐波那契数列
F
(
n
)
=
{
1
,
n
=
0
,
1
F
(
n
−
1
)
+
F
(
n
−
2
)
,
n
>
1
F(n) =\left\{ \begin{matrix} 1, \quad n=0,1 \\ F(n-1)+F(n-2),n>1 \end{matrix} \right.
F(n)={1,n=0,1F(n−1)+F(n−2),n>1
有两种常用的算法：递归算法和非递归算法，根据不同算法分析它的时间复杂度。
递归算法
int fibo(int n){
if(n<=1) return 1;
return fibo(n-1)+fibo(n-2);
}
分析如下：
(1) 使用公式进行递推
T
(
n
)
=
1
+
T
(
n
−
1
)
+
T
(
n
−
2
)
=
1
+
2
+
T
(
n
−
2
)
+
2
T
(
n
−
3
)
+
T
(
n
−
4
)
=
1
+
2
+
4
+
T
(
n
−
3
)
+
3
T
(
n
−
4
)
+
3
T
(
n
−
5
)
+
T
(
n
−
6
)
.
.
.
=
2
0
+
2
1
+
.
.
.
+
2
k
−
1
+
T
(
n
−
k
)
+
k
T
(
n
−
k
−
1
)
+
.
.
.
+
k
T
(
1
)
+
T
(
0
)
=
2
0
+
2
1
+
.
.
.
+
2
k
−
1
+
[
2
k
−
k
−
1
)
]
+
T
(
n
−
k
−
1
)
+
(
k
+
1
)
T
(
n
−
k
−
k
−
1
)
+
.
.
.
+
x
1
T
(
1
)
+
y
1
T
(
0
)
.
.
.
=
[
2
0
+
2
1
+
.
.
.
+
2
k
−
1
+
2
k
+
.
.
.
+
2
n
−
1
]
−
[
k
+
1
+
x
1
+
y
1
+
.
.
.
+
x
n
−
k
−
1
+
y
n
−
k
−
1
]
+
x
n
−
k
T
(
1
)
+
y
n
−
k
T
(
0
)
T(n)=1+T(n-1)+T(n-2)\\=1+2+T(n-2)+2T(n-3)+T(n-4)\\=1+2+4+T(n-3)+3T(n-4)+3T(n-5)+T(n-6)\\...\\=2^0+2^1+...+2^{k-1}+T(n-k)+kT(n-k-1)+...+kT(1)+T(0)\\=2^0+2^1+...+2^{k-1}+[2^k-k-1)]+T(n-k-1)+(k+1)T(n-k-k-1)+...+x_1T(1)+y_1T(0)\\...\\=[2^0+2^1+...+2^{k-1}+2^k+...+2^{n-1}]-[k+1+x_1+y_1+...+x_{n-k-1}+y_{n-k-1}]+x_{n-k}T(1)+y_{n-k}T(0)
T(n)=1+T(n−1)+T(n−2)=1+2+T(n−2)+2T(n−3)+T(n−4)=1+2+4+T(n−3)+3T(n−4)+3T(n−5)+T(n−6)...=20+21+...+2k−1+T(n−k)+kT(n−k−1)+...+kT(1)+T(0)=20+21+...+2k−1+[2k−k−1)]+T(n−k−1)+(k+1)T(n−k−k−1)+...+x1T(1)+y1T(0)...=[20+21+...+2k−1+2k+...+2n−1]−[k+1+x1+y1+...+xn−k−1+yn−k−1]+xn−kT(1)+yn−kT(0)
因为时间复杂度算的是最坏情况下的时间复杂度，所以计算第一个括号内的即可
即
T
(
n
)
=
O
(
2
n
)
T(n)=O(2^n)
T(n)=O(2n)
(2) 利用树求解
参考
我们可以将斐波那契数列的求解画成一棵树，树有叶子节点和非叶子节点。
其中叶子节点就是F(1)和F(0)，直接返回结果，有F(n)个；
而非叶子节点就是求解过程中要用到的F(n-1),F(n-2)…，对调用函数得到的结果相加，有F(n)-1个。
因为非叶子节点就是由它的左右节点相加得来的，所以根节点本质上就是所有叶子节点相加的结果，非叶子节点的个数就与加号的个数相等，也就是比叶子节点数少1。
T
(
n
)
=
F
(
n
)
+
F
(
n
)
−
1
T(n)=F(n)+F(n)-1
T(n)=F(n)+F(n)−1
斐波那契的通项公式为
F
(
n
)
=
1
5
[
(
1
+
5
2
)
n
−
(
1
−
5
2
)
n
]
F(n)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]
F(n)=51[(21+5)n−(21−5)n]
即
T
(
n
)
=
O
(
F
(
n
)
)
=
O
(
(
1
+
5
2
)
n
)
T(n)=O(F(n))=O((\frac{1+\sqrt{5}}{2})^n)
T(n)=O(F(n))=O((21+5)n)
非递归算法
// 这里为了方便理解用了数组
int f[n+1];
f[0]=f[1]=1;
int i=2;
while(i<=n){
f[i]=f[i-1]+f[i-2];
i++;
}
这里直接累加次数就可以了，f[i]=f[i-1]+f[i-2]的次数就是主体语句的执行次数t，因此有t=n-1，则 T ( n ) = O ( n ) T(n)=O(n) T(n)=O(n)
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
33
0- 0
已为社区贡献1条内容
所有评论(0)