1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
|
import numpy import time
class : '''1.递归法''' def fib_recur(self, n): assert n >= 0, "n >= 0" if n in (0, 1): return n return self.fib_recur(n - 1) + self.fib_recur(n - 2)
'''2.memorization''' memo = {0: 0, 1: 1} def fib_recur_memo(self, n): if not n in Solution.memo: Solution.memo[n] = self.fib_recur_memo(n-1) + self.fib_recur_memo(n-2) return Solution.memo[n]
'''3.递推法''' def fib_loop(self, n): a, b = 0, 1 for i in range(n): a, b = b, a + b return a
'''4.yield''' def fib_yield(self, n): a, b = 0, 1 for i in range(n): a, b = b, a + b yield a
'''5.矩阵法''' def fib_matr(self, n): res = (numpy.matrix([[1, 1], [1, 0]]) ** (n - 1) * numpy.matrix([[1], [0]])) return res[0, 0]
'''6.矩阵法''' def fib_matr_pow(self, n): res = pow(numpy.matrix([[1, 1], [1, 0]]), n - 1) * numpy.matrix([[1], [0]]) return res[0, 0]
'''7.类实现内部魔法方法''' class Fibonacci(object): def __init__(self, num): self.num = num
def __iter__(self): if self.num < 1: return 1 a, b = 0, 1 while self.num > 0: a, b = a + b, a self.num -= 1 yield a
def __next__(self): return self.__iter__()
if __name__ == "__main__": n = 45 t1 = time.clock() print(Solution().fib_recur(n)) t2 = time.clock() print("recursion time : ", t2 -t1)
t1 = time.clock() print(Solution().fib_recur_memo(n)) t2 = time.clock() print("recursion memo time : ", t2 - t1)
t1 = time.clock() print(Solution().fib_loop(n)) t2 = time.clock() print("loop time : ", t2 - t1)
t1 = time.clock() print(Solution().fib_yield(n).__next__()) t2 = time.clock() print("yield time : ", t2 - t1)
t1 = time.clock() print(Solution().fib_matr(n)) t2 = time.clock() print("matrix time : ", t2 - t1)
t1 = time.clock() print(Solution().fib_matr_pow(n)) t2 = time.clock() print("matrix (pow) time : ", t2 - t1)
t1 = time.clock() print(Fibonacci(n).__iter__().__next__()) t2 = time.clock() print("class time : ", t2 - t1)
|
近期评论