[已解决]python利用装饰器计算递归函数（斐波那契）的运行时间

zerotwo020202

print("统计使用普通递归，优化尾递归，以及迭代计算斐波那契数列的运行时间")
print("\n-------装饰器计算函数运行时间-------")
import time
def typefunc(name):
    def time_master(func):
        def call_func(*args, **kwargs):
            start = time.time()
            print(func(*args, **kwargs))
            stop = time.time()
            print(f"{name}耗时：{(stop - start):.9f}秒。")
        return call_func
    return time_master



print("\n-------普通递归-------")
@typefunc("普通递归")
def FibRecur(n):
    def fibRecur(n):
        if n == 1 or n == 2:
            return 1
        else:
            return fibRecur(n - 1) + fibRecur(n - 2)
    return fibRecur(n)

print("\n-------优化尾递归-------")
@typefunc("优化尾递归")
def TailfibRecur(n):
    def tailfibRecur(n, total1 = 1, total2 = 1):
        if n == 1 or n == 2:
            return total1
        else:
            return tailfibRecur(n - 1, total1 + total2, total1)
    return tailfibRecur(n)

print("\n-------普通迭代-------")
@typefunc("普通迭代")
def fibIter(n):
    a = 1
    b = 1
    c = 1
    if n == 1 or n == 2:
        return 1
    while n > 2:
        c = a + b
        a = b
        b = c
        n -= 1
    return c

FibRecur(40)
TailfibRecur(120)
fibIter(120)


102334155
普通递归耗时：10.075566292秒。
5358359254990966640871840
优化尾递归耗时：0.000999928秒。
5358359254990966640871840
普通迭代耗时：0.000000000秒。

请问大佬，这个时间结果正确吗？打印的值应该是正确的，为什么跟小甲鱼课后作业答案差距这么大

最佳答案

月排行榜 / 总排行榜

歌者文明清理员

2023-4-18 17:46:38

根据你提供的代码和结果，优化尾递归和普通迭代计算斐波那契数列的运行时间是正确的，但是普通递归计算斐波那契数列的运行时间较长，需要10.075566292秒。这是因为普通递归的实现方式是对每个数都调用一次自身函数，导致时间复杂度呈指数级别增长。通过优化后的尾递归和迭代实现可以避免重复计算，时间复杂度更低。至于答案与小甲鱼课后作业的差距，可能是因为不同的 Python 版本或者环境配置导致的。

跳转到最佳答案楼层

歌者文明清理员

根据你提供的代码和结果，优化尾递归和普通迭代计算斐波那契数列的运行时间是正确的，但是普通递归计算斐波那契数列的运行时间较长，需要10.075566292秒。这是因为普通递归的实现方式是对每个数都调用一次自身函数，导致时间复杂度呈指数级别增长。通过优化后的尾递归和迭代实现可以避免重复计算，时间复杂度更低。至于答案与小甲鱼课后作业的差距，可能是因为不同的 Python 版本或者环境配置导致的。

zerotwo020202

歌者文明清理员 发表于 2023-4-18 17:46
根据你提供的代码和结果，优化尾递归和普通迭代计算斐波那契数列的运行时间是正确的，但是普通递归计算斐波 ...

好的，谢谢

歌者文明清理员

zerotwo020202 发表于 2023-4-18 19:33
好的，谢谢

不客气~欢迎继续提问