import time
def fib_slow(n):
assert n > 0, "n > 0"
if n == 1 or n == 2:
return 1
return fib_slow(n - 2) + fib_slow(n - 1)
def fib_fast1(n):
assert n > 0, "n > 0"
if n == 1 or n == 2:
return 1
else:
a, b = 1, 1
for _ in range(n - 2):
a, b = b, a + b
return b
def fib_gen(n):
assert n > 0, "n > 0"
if n == 1 or n == 2:
yield 1
else:
i, a, b = 0, 0, 1
while i < n:
a, b = b, a+b
yield a
i = i + 1
num = 500000
start_time = time.time()
result = fib_slow(num)
print('result: %d' % result)
end_time = time.time()
print('fib_slow time used: %d' % (end_time-start_time))
start_time = time.clock()
result = fib_fast1(num)
print('result: %d' % result)
end_time = time.clock()
print('fib_fast1 time used: %f' % (end_time - start_time))
start_time = time.clock()
for index, fib_number in enumerate(fib_gen(num)):
if index == num-1:
print(fib_number)
end_time = time.clock()
print('\nfib_gen time used: %f' % (end_time-start_time))
运行的结果如下：
result: 102334155
fib_slow time used: 45
result: 102334155
fib_fast1 time used: 0.000038
第一种递归的方式重复了大量计算，仅仅是计算第40个数就已经用了45秒
第二种递推的方式在数字为50万的时候，时间达到了3秒
num = 500000
result: 29555614082695151...
fib_fast1 time used: 3
第三种写成了生成器，可以返回所有的fib值
num = 500000
fib_gen time used: 4.244906
