时间戳

首页 > 解决方案 > 降低阶梯式问题的时间复杂度（亚马逊面试问题）

python - 降低阶梯式问题的时间复杂度（亚马逊面试问题）

问题描述

def step(n):
    if (n==0) or (n==1):
        return 1 
    elif n==2:
        return 2
    else:
        return step(n-1) + step(n-2) + step(n-3)
n = int(input())
print(step(n))

对于输入 53798080，它需要 1 秒。它应该比满足测试用例要少得多。

标签： pythonrecursion

解决方案

对于输入 53798080，它需要 1 秒。

我非常怀疑这一点。您的代码堆栈在此输入上溢出。我相信这里发生的是输入30需要 1 秒才能产生输出53798080。通过输入 31，我们最多需要半分钟。

如果我们记住您的代码：

from functools import lru_cache

@lru_cache
def step(n):
    if n == 0 or n == 1:
        return 1

    if n == 2:
        return 2

    return step(n-1) + step(n-2) + step(n-3)

正如@templatetypedef 解释的那样，它解决了速度问题。但是，它会在输入 500 以上时因堆栈溢出（假设您没有分配更多堆栈）而爆炸。我们可以将该范围加倍，并使用更有效且递归更少的算法来处理速度问题而无需记忆：

def step(n, prev1=2, prev2=1, prev3=1):
    if 0 <= n <= 1:
        return 1

    if n == 2:
        return prev1

    return step(n - 1, prev3 + prev2 + prev1, prev1, prev2)

这将处理高达 999 的输入并在几分之一秒内产生结果：

> time python3 test.py
1499952522327196729941271196334368245775697491582778125787566254148069690528296568742385996324542810615783529390195412125034236407070760756549390960727215226685972723347839892057807887049540341540394345570010550821354375819311674972209464069786275283520364029575324
0.032u 0.011s 0:00.04 100.0%    0+0k 0+0io 0pf+0w
>

（添加@lru_cache到此代码中会将输入范围缩小回原来的范围，并且在速度方面没有区别。）

推荐阅读