时间戳

首页 > 解决方案 > 为什么网格旅行者的时间复杂度为 2^(n+m)？

python - 为什么网格旅行者的时间复杂度为 2^(n+m)？

问题描述

网格旅行者

def grid_traveller(n,m):
    if n == 0 or m == 0: return 0
    if n == 1 and m == 1: return 1
    return grid_traveller(n-1,m), grid_traveller(n,m-1)

一个例子：

         2,2
       /     \
    1,2       2,1
   /   \      /  \
0,2     1,1  1,1  2,0

虽然我可以提出解决方案，但我对深度和时间复杂度感到困惑。深度应该是 n+m，因为一次只能减少 n 或 m，因此需要 n+m 步才能达到 (0,0)。这听起来合乎逻辑，但深度到底意味着什么？在这种情况下，树的高度为 3（而不是 2+2=4），递归调用的次数为 2（(1,2) 和 (2,1)），那么深度告诉我们什么？我曾经认为深度=递归树的高度（至少对于单个输入），但我不确定我是否有正确的想法。

我想如果我对深度有更多了解，我可能会弄清楚为什么时间复杂度是 2^(n+m)，但也可以随意解释一下。

标签： pythondynamic-programming

解决方案

我被一个问题弄糊涂了，我不清楚我不明白什么。我认为让我失望的是 Ry- 的评论。

即使实际堆栈深度与您正在分析的树不同，复杂性也是相同的。

当我发布这个问题时，我拒绝了 height = n+m 的想法（以及其他一些我现在不知道为什么的自我困惑），但没有注意到我起草的示例都有 height = n + 的简单模式米 -1。

所以现在我已经重新接受了深度 = 树的高度 = n+m，我可以继续轻松地接受时间复杂度。为了完整起见，这是我的解释：

递归深度也称为递归树的高度。时间复杂度为 2^(n+m)，因为对于树的每一层，我们必须使函数调用的数量加倍 (1 -> 2 -> 4 -> 8 -> 16)。

对于高度为 3 的树（在此示例中），我们必须进行 2^3=8 次调用（如果您感到困惑，请计算上面的节点！）。
对于高度为 (n+m-1) 的树，我们必须进行 2^(n+m-1)~=2^(n+m) 次调用（因为当 n+m 接近无穷大时，常数是微不足道的）。

推荐阅读