欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

牺牲空间来优化时间

程序员文章站 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)}')