为什么grid traveler的时间复杂度是2^(n+m)？

Question

网格旅行者

Returns 从 n x 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) and (2,1)), 所以深度告诉我们什么？我曾经认为深度=递归树的高度（至少对于单个输入），但我不确定我的想法是否正确

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

Answer 1

我被一个问题弄糊涂了，我不清楚我不明白的地方。我认为让我震惊的是 Ry- 的评论。

The complexity is the same even if the actual stack depth is different from the tree you’re analyzing by a constant offset.

当我发布这个问题时，我拒绝了 height = n+m 的想法（以及其他一些我现在不知道为什么的自我混淆）但没有注意到我起草的所有示例的简单模式身高 = n + m -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 接近无穷大时，常数是微不足道的）。

为什么grid traveler的时间复杂度是2^(n+m)？

Why does grid traveller have a time complexity of 2^(n+m)?

python

dynamic-programming