实现斐波那契数列

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