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

Question

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

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Input: 2

Output: 2

Explanation: There are two ways to climb to the top.

1 step + 1 step

2 steps

我的算法：

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 的楼梯的解数是 exactly equal to the nth Fibonacci number，而第 n 个斐波那契数恰好是 Θ(φⁿ)。所以这意味着总共进行了 Θ(φⁿ) 次递归调用。

那么这些递归调用需要多少工作量？我们可以保守地将每个递归调用的工作上限设置为 O(n)，因为在最坏的情况下，对列表求和会加起来 1 + 1 + 1 + ... + 1 n 次。但是我们也可以在 Ω(n) 处降低在叶子上完成的功，那里的功最大，因为在最好的情况下，我们将 2 + 2 + ... + 2 加起来总共 n / 2 次。

总的来说，我们有 Θ(φⁿ) 次调用，其中底部的调用每次执行 Θ(n) 次，总共 Θ(n · φⁿ) 工作。

还有最后一个细节需要解决 - "overshoot" 加起来大于 n 的递归调用怎么样？事实证明，其中也有 O(φⁿ)。一种理解方式是，过冲达到 n + 1 的方式的数量至多是列出所有大小为 n + 1 的路径的解决方案的数量，并且有 O(φⁿ）这些。所以把这些加回去不会改变任何东西。

希望对您有所帮助！

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

Time complexity of listing all paths down stairs?

algorithm

big-o

backtracking

time-complexity