文章目录
- 0.前言
- 1. Fibonacci数应用
- 1.1 fib():递归
- 1.1.1 问题与代码
- 1.1.2 复杂度分析
- 1.1.3 递归分析
- 1.2 fib():迭代
0.前言
make it work,make it right,make it fast.
让代码能够不仅正确而且足够高效地运行。
1. Fibonacci数应用
1.1 fib():递归
1.1.1 问题与代码
上述fib()算法运行地较慢
__int64 fib ( int n ) { //计算Fibonacci数列的第n项(二分递归版):O(2^n)
return ( 2 > n ) ?
( __int64 ) n //若到达递归基,直接取值
: fib ( n - 1 ) + fib ( n - 2 ); //否则,递归计算前两项,其和即为正解
}
CPU资源未被占满,进程在满负荷运行,但是依然运行地非常非常慢。
1.1.2 复杂度分析
上述推导看复杂度为指数(
2
n
2^n
2n)
估算下
ϕ
43
\phi^{43}
ϕ43 =
2
30
2^{30}
230 =
1
0
9
10^{9}
109flo = 1 sec(计算工作量大概可以用10地9次方条基本操作指令来度量,10的9次方就是现在主流计算机主频的cpu在1s中大致能够吞吐的计算量,亦是fib(43)计算大概需要1s)
1.1.3 递归分析
使用第二种手段对上述代码进行分析
**每个递归实例从原理上来讲只需要计算一次。**诀窍和改进放在也在于此。
1.2 fib():迭代
方法A:
将Fibonacci数的各项所计算的结果制作成一个表格,将每项计算结果存入表中,每次需要递归实例的时候便可以查表获取。智能屏蔽此次和后续调用。在O(1)时间内返回结果。
方法B:
计算方向为自小而大,自底而上,这样由原来的递归算法改进为迭代型算法,同样可以完成刚才工作。如果比作上楼梯,那么在每个台阶上只需停留一次。
例如fib(5):
f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(2) = f(1) + f(0)
f(1) = f(0) + f(-1)
迭代的计算是自底而上,所以是算f(1) f(2) f(3)f(4) f(5)
g = g+f 等同于 f(1) = f(0) + f(-1) 再迭代
g = g+f 等同于 f(2) = f(1) + f(0) ,
这次f(0)是未知的,所以f = g-f就是算出下次迭代的末项f(0)
f(0) = f(1) - f(-1) 等同于 f = g-f
具体的代码分析可以参考Fibonacci数