我无法确定爬楼梯问题的回溯解决方案的时间复杂度
您正在爬楼梯。它需要n步才能到达顶部。
每次您可以爬1或2步。您可以通过几种不同的方式登顶？
注意：给定n将为正整数。
输入：
2输出：
2说明：有两种爬上顶部的方法。
- 1步+1步
- 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)}
此功能的运行时是不寻常的Θ（N·φ Ñ），其中φ是黄金比例，（1 +√5）/ 2。
要了解为什么会出现这种情况，让我们讨论一下如何分析您编写的代码。想象一下此代码的递归树。（这是每个递归调用都具有一个节点的树）。请注意，每个递归调用都分支-一个调用大小为n-1的子问题，一个子调用大小为n-2的问题。在每个内部节点都在分支的树中，总节点数最多是n的两倍。叶数。在您的情况下，找到的每个解决方案都有一个叶子，当递归超过n的值时，还有一些其他叶子。（目前，我们将忽略第二个组，但稍后将讨论原因。）这意味着递归调用的总数最多为路径数的两倍（稍后将讨论前一个警告）。下楼梯。
那么有多少解决方案可以解决这个问题呢？事实证明，解决方案的高度的阶梯数量n被恰好等于第n个Fibonacci数，和第n Fibonacci数恰好是Θ（φ Ñ）。这样就意味着总共有Θ（φ是ñ）总递归调用制成。
那么这些递归调用需要做多少工作？我们可以保守地将每个递归调用的工作上限设置为O（n），因为在最坏的情况下，将列表相加会累加1 +1 + 1 + ... + 1 n次。但是，我们也可以将在最大的叶子处的工作以Ω（n）进行下界，因为在最佳情况下，我们将2 + 2 + ... + 2总计为n / 2倍。
总体而言，我们有Θ（φ ñ）调用，它的底部做那些Θ（n）的各项工作，共计Θ（N·φ的ñ）工作。
有最后一个要解决的细节-“超调”并加起来大于n的递归调用呢？原来，这里还有O（φ ñ这些）为好。看到这一点的一种方式是，过冲打N + 1的方式的数量是最多的解决方案的数量，规模上市N + 1的所有路径，并有O（φ ñ）的这些。因此，将它们重新添加不会改变任何内容。
希望这可以帮助！
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句