你看看你递归代码的复杂度 是O(2^n) 而第二个的复杂度是O(n) 运行效率当然不同
COUNTER = 0
def fibn(n):
global COUNTER
COUNTER += 1
if n == 0:
return 1
elif n == 1:
return 1
else:
return fibn(n-1) + fibn(n-2)
statistics = []
for i in range(35):
COUNTER = 0
fibn(i + 1)
statistics.append(((i + 1), COUNTER))
print statistics[(1, 1), (2, 3), (3, 5), (4, 9), (5, 15), (6, 25), (7, 41), (8, 67), (9, 109), (10, 177), (11, 287), (12, 465), (13, 753), (14, 1219), (15, 1973), (16, 3193), (17, 5167), (18, 8361), (19, 13529), (20, 21891), (21, 35421), (22, 57313), (23, 92735), (24, 150049), (25, 242785), (26, 392835), (27, 635621), (28, 1028457), (29, 1664079), (30, 2692537), (31, 4356617), (32, 7049155), (33, 11405773), (34, 18454929), (35, 29860703)]
做了一个简单的proflie
import cProfile
import pstats
def fibn(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return fibn(n-1) + fibn(n-2)
print ' i, calls, time'
for i in range(50):
pr = cProfile.Profile()
pr.enable()
fibn(i)
pr.disable()
stats = pstats.Stats(pr)
stats.strip_dirs()
st = stats.stats[('test1.py', 3, 'fibn')]
print '%3d,%10d,%8f' % (i, st[1], st[3])i, calls, time
0, 1, 0.000000
1, 1, 0.000001
2, 3, 0.000003
3, 5, 0.000005
4, 9, 0.000008
5, 15, 0.000012
6, 25, 0.000020
7, 41, 0.000033
8, 67, 0.000165
9, 109, 0.000088
10, 177, 0.000141
11, 287, 0.000228
12, 465, 0.000450
13, 753, 0.000601
14, 1219, 0.001016
15, 1973, 0.003561
16, 3193, 0.002593
17, 5167, 0.004372
18, 8361, 0.007097
19, 13529, 0.011073
20, 21891, 0.018552
21, 35421, 0.032467
22, 57313, 0.051762
23, 92735, 0.095383
24, 150049, 0.133490
25, 242785, 0.212390
26, 392835, 0.352861
27, 635621, 0.578204
28, 1028457, 0.987839
29, 1664079, 1.506812
30, 2692537, 2.682802
31, 4356617, 3.998936
32, 7049155, 8.089419
33, 11405773, 13.058235
34, 18454929, 23.930004
35, 29860703, 36.503880
目测fibn(50)要算出来需要两周
递归函数斐波那契数列python_使用Python函数递归实现斐波那契数列时为什么运行速度很慢？...
如果觉得《递归函数斐波那契数列python_使用Python函数递归实现斐波那契数列时为什么运行速度很》对你有帮助，请点赞、收藏，并留下你的观点哦！
