为什么网格旅行者具有2^(n+m)的时间复杂度?

Question

Grid traveler

• 返回从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)，但也请随意解释。

Answer 1

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

复杂性是相同的，即使实际的堆栈深度与你通过常量偏移量分析的树不同。

当我张贴这个问题时，我拒绝了高度= 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趋于无穷时常数是不重要的)

Answer 2

我会尽量给出更直观的解释。例如:n = 3, m = 3;网格是

1 2 3
4 5 6
7 8 9

从0,0开始的选项就像这样

1
/     
4       2
/       /  
7    5   5   3   
/ 
8   ...
/
9

懒得做整棵树。但你能看到的深度是n+m-1

或3 + 3 -1 = 5因此遍历这个树

的复杂度= O(节点)

= 0 (2^(n+m-1) -1)

~ O (2 ^ (n + m))

p。如有需要，请随时更正。:)