首页
社区
课程
招聘
[原创]递归计算斐波那契数列时间复杂度之彻底分析
发表于: 2010-10-21 17:10 48715

[原创]递归计算斐波那契数列时间复杂度之彻底分析

2010-10-21 17:10
48715

以前看数据结构与算法分析(C语言描述),作者在讲述算法分析时提到递归计算斐波那契数列,
Fib(int N)
{
        if(N <= 1)
                return 1;
        else
                return Fib(N - 1) + Fib(N-2);
}

时间复杂度T(N) = T(N-1) + T(N-2);
作者说归纳法易证得T(N) >= Fib(N);而Fib(N) < (5/3)^(N);类似计算可正得Fib(N)>= (3/2)^(N)
这个地方作者处理得有些不太彻底,不是吗?翻来覆去没把Fib(N)准确求出,今天我翻看另一本资料,
更模糊了,它求得2^(N/2) < T(N) < 2^(N)就完事了。
不过今天我开窍了,T(N) = T(N-1) + T(N-2);这是什么?也许你会说这是一个递推式,但它的学名是
二阶齐次差分方程,我今天猛然看出这一点:)!
什么是差分方程?
以下资料全部来自Introduction to Numerical Analysis,second Edition Translate by
Bartels,W.Gautsch and C.Witigall,Springer-Verlag,世界图书出版公司,(英文版)

这是我大三所用的数值分析教材,目前国内好像还没中文版。

书上464页说道:
By a linear homogeneous difference equation of order r one means an equation of the form

u(j+r) + a(r-1)u(j+4-1) + .... + a(0)u(j) =0;        j=0,1,2...        (7.2.9.1)
上面那些括号里的数一般是下标,我不好打出来,用括号代替了。

反正就是说齐次差分方程就是那个式子的形式了。
接着466页上讲到
Theorem. let the polynomial
Ψ(u) = u^r + a(r-1)u^(r-1) + ... + a(0)
have the k distinct zeros λ(i) ,i = 1,2,...,k
with multiplicities σ(i),i = 1,2,...,k
and let a(0) != 0,then for arbitray polynomials p(i)(t) with deg p(i) < σ(i),i = 1...k;
the sequence
u(j) = p(1)(j)λ(1)^(j) + p(2)(j)λ(2)^(j) +...+ p(k)(j)λ(k)^(j)
is a solution of the difference eqution (7.2.9.1).Conversely,every solution of
(7.2.9.1)can be uniquely represented in the form(7.2.9.9).

这段话又是什么意思呢?一句话:这是个牛逼的定理它导出了齐次差分方程的解并且说明了齐次差分方程
的所有解的形式。书上证明不是太短。

接下来举例说明。就拿斐波那契数列来说。
书上561页提了个问题,问题我就不打了,它问:
u(j+2) = u(j+1) + u(j)的通项公式是什么?然后它说u(0) = 0,u(1) = 1 即可得Fibonacci sequence
就是说这个式子从u(0) = 0,u(1) = 1递推即可得斐波那契数列。从其他初始状态的话可得其他数列。

开始解决问题。
按照那个牛逼定理,先解方程x^2 - x - 1 = 0;
这个不难,x1= (1+5^(1/2))/2,x2 = (1-5^(1/2))/2;
然后套公式u(j) = c1 * x1^(j) + c2 * x2^(j);
c1,c2为待定常数,利用u(0) = 0,u(1) = 1,得出c1 = 1/(5^(1/2));c2 = -c1;
这样斐波那契数列的通项就出来了,递归计算斐波那契数列时间复杂度问题也就迎刃而解了。


[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

收藏
免费 7
支持
分享
最新回复 (8)
雪    币: 92
活跃值: (16)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
一个所有学过线性代数都会的“特征方程”解线性递推式的方法 撑起了 楼主的这篇文章。。。
2010-10-21 17:35
0
雪    币: 208
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
递归算法重复求解数太大。。
2010-10-21 18:59
0
雪    币: 1259
活跃值: (38)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
stu
4
楼上好ID.
2010-10-21 21:11
0
雪    币: 678
活跃值: (101)
能力值: ( LV2,RANK:150 )
在线值:
发帖
回帖
粉丝
5
这种题目转化为递推也是效率很不错的,这就是动态规划的思想,以空间换时间,当然后面的那种数学方法就更加不用说了。效率和空间都是无敌。就像用数学方法解约瑟夫环问题一样,学习算法首推《算法导论》。
2010-10-21 22:18
0
雪    币: 354
活跃值: (157)
能力值: ( LV7,RANK:100 )
在线值:
发帖
回帖
粉丝
6
真是不好意思,学了就忘。不过特征方程又怎么来的呢?不可能是现成的吧。
2010-10-21 23:34
0
雪    币: 92
活跃值: (16)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
7
其实楼主你最后的方法看上去挺好,但有个致命弱点,就是精度问题。

既然是 根式的n次方,那么在进行乘方运算后必然精度不准。

其实,斐波那契数列的计算机算法正确的应该是 矩阵快速幂相乘。

设矩阵[C] 为:
1 1 0
1 0 1
1 0 0

则矩阵 (f[n] f[n-1] f[n-2]) = (1 1 2)*[C]^(n-1)

快速幂的意思是: [c]^n = ([c]^2)^n/2  这样用分治算法可以使时间复杂度降为O( logn )
2010-10-29 18:01
0
雪    币: 468
活跃值: (52)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
8
高中代数,关于线性数列求解
2010-10-30 08:38
0
雪    币: 354
活跃值: (157)
能力值: ( LV7,RANK:100 )
在线值:
发帖
回帖
粉丝
9
[QUOTE=Dsh骗天;880755]其实楼主你最后的方法看上去挺好,但有个致命弱点,就是精度问题。

既然是 根式的n次方,那么在进行乘方运算后必然精度不准。

其实,斐波那契数列的计算机算法正确的应该是 矩阵快速幂相乘。

设矩阵[C] 为:
1 1 0
1 0 1
1 0 0

则矩阵 (f[n] f[n...[/QUOTE]

受教了!谢谢!
2010-10-30 11:57
0
游客
登录 | 注册 方可回帖
返回
//