列出所有下楼梯的时间复杂度？

Question

我无法确定陈述爬楼梯问题的回溯解决方案的时间复杂度

您正在爬楼梯。它需要n步才能到达顶部。

每次您可以爬1或2步。您可以通过几种不同的方式攀登顶部？

注意：给定n将是一个正整数。

输入：2

输出：2

说明：有两种方法可以爬到顶部。

1. 1步+ 1步
2. 2个步骤

我的算法：

input = [1, 2]
output = set()
n = 4
def helper(temp):
    if sum(temp) == n:
        output.add(tuple(temp))
    elif sum(temp) > n:
        return
    else:
        for i in input:
            helper(temp + [i])
helper([])

print(output)

n的输出= 4：

{(1, 2, 1), (2, 1, 1), (1, 1, 2), (2, 2), (1, 1, 1, 1)}

Answer 1

此函数的运行时是不寻常的Θ（n·φⁿ），其中φ是黄金比例，（1 +√5）/ 2。

要了解为什么会这样，让我们​​谈谈如何分析您编写的代码。想象一下此代码的递归树。 （那是每个递归调用都有一个节点的树）。请注意，每个递归调用都分支-一个调用大小为n-1的子问题，一个子调用大小为n-2的问题。在每个内部节点都在分支的树中，总节点数最多是n的两倍。叶数。在您的情况下，找到的每个解决方案都有一个叶子，当递归超过n的值时，还有一些其他叶子。 （目前，我们将忽略第二组，但稍后再讨论原因。）这意味着递归调用的总数最多为路径数的两倍（稍后将讨论前一警告）下楼梯。

那么这个问题有多少解决方案？事实证明，高度为n的楼梯的解数为exactly equal to the nth Fibonacci number，第n个斐波纳契数恰好是Θ（φⁿ）。因此，这意味着总共进行了Θ（φⁿ）个递归调用。

那么这些递归调用需要多少工作？我们可以保守地在O（n）处限制每个递归调用的工作，因为在最坏的情况下，将列表相加会导致1 +1 + 1 + ... + 1 n次。但是我们也可以将在最大的叶子处所做的功限制在Ω（n）处，因为在最佳情况下，我们将2 + 2 + ... + 2合计为n / 2倍。

[总体上，我们有Θ（φⁿ）个调用，其中最下面的一个每个都执行Θ（n）工作，总共有Θ（n·φⁿ）个工作。

还有最后一个要解决的细节-“超调”并加起来大于n的递归调用怎么办？事实证明，它们中也有O（φⁿ）。看到这种情况的一种方法是，超调达到n + 1的方式最多是列出大小为n + 1的所有路径的解决方案的数量，其中有O（φⁿ）。因此，重新添加这些不会改变任何内容。

希望这会有所帮助！