为什么网格旅行者的时间复杂度为2^（n+m）？

Question

网格移动器

• 返回从nx 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），但也可以随意解释一下

Answer 1

我被一个问题弄糊涂了，我不清楚什么是我不明白的。我想让我大吃一惊的是瑞的评论

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

当我发布这个问题时，我拒绝了高度=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接近无穷大时，常数不重要）