牺牲空间来优化时间
程序员文章站
2022-12-22 15:34:46
算例:生成Fibonacci数列 【方法一】秒出结果! 【方法二】时间消耗特别长! 【方法二改进】时间与空间不可兼得,要想优化时间,那就增加额外的存储空间! ......
算例:生成fibonacci数列
【方法一】秒出结果!
1 a, b = 0, 1 2 for num in range(1, 101) 3 a, b = b, a + b 4 print(f'{num}: {a}')
【方法二】时间消耗特别长!
def fib(num): if num in (1, 2): return 1 return fib(num - 1) + fib(num - 2) for num in range(1, 101): print(f'{num}: {fib(num)}')
【方法二改进】时间与空间不可兼得,要想优化时间,那就增加额外的存储空间!
1 def fib(num, temp = {}) 2 if num in (1, 2): 3 return 1 4 if num not in temp: 5 temp[num] = fib(num - 1) + fib(num - 2) 6 return temp[num] 7 8 for num in range(1, 101) 9 print(f'{num}: {fib(num)}')
推荐阅读