时间戳

首页 > 解决方案 > 列出所有下楼梯路径的时间复杂度？

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

问题描述

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

你正在爬楼梯。到达顶部需要 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)}

标签： algorithmtime-complexitybig-obacktracking

解决方案

这个函数的运行时间是不寻常的 Θ(n · φ n )，其中 φ 是黄金比例，(1 + √5) / 2。

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

那么这个问题有多少解决方案呢？事实证明，高度为 n 的楼梯的解数正好等于第 n 个斐波那契数，而第 n 个斐波那契数恰好是 Θ(φ n )。所以这意味着总共有 Θ(φ n ) 的总递归调用。

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

总的来说，我们有 Θ(φ n ) 调用，其中底部的调用每个都做 Θ(n) 工作，总共有 Θ(n · φ n ) 工作。

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

希望这可以帮助！

推荐阅读