在仅向下或向右移动时，在 MxN 网格中从左上角到达右下角的方法数。什么是时间和 space 复杂度？

Question

问题: 在 MxN 网格中找到从左上角到右下角的多种可能方式，而你只能向下或向右移动。

这是我写的两个算法。结果看起来不错，但我无法计算出时间和 space 复杂性，我对复杂性可能是什么有一些猜测，但我无法以“正确”的方式证明它们。

朴素算法：

    function gridTravel(m, n) {
      if(m<1 || n<1) return 0;
      if (m === 1 || n === 1) return 1;
      return gridTravel(m-1, n) + gridTravel(m, n-1);
    };
    console.log(gridTravel(10,10));

我的猜测:

Space 复杂度 - O(n+m)？最长可能的调用堆栈似乎是“线性”缩放的，所以假设一些近似值是 O(n+m)，但我无法真正证明或反驳它。
时间复杂度是指数级的，因为每个位置可以创建 2 个新位置 - O(2^n) 或 O(2^n+m)，不确定哪个更合适。

                   m:n
        m-1:n                m:n-1
    m-2:n  m-1:n-1     m-1:n-1   m:n-2

但是，我再次对这个解释没有信心，因为它不是对称树，它只是一开始看起来像。

朴素算法 + 记忆：


    seenGrids = {};
    const gridTravel = (m, n) => {
      if(m<1 || n<1) return 0;
      if (m === 1 || n === 1) return 1;
      if (`${m}:${n}` in seenGrids || `${n}:${m}` in seenGrids) {
        return seenGrids[`${m}:${n}`] || seenGrids[`${n}:${m}`];
      }
      seenGrids[`${m}:${n}`] = gridTravel(m-1, n) + gridTravel(m, n-1);
      return seenGrids[`${m}:${n}`];
    };

我的猜测：

Space - O(n*m)？调用堆栈似乎仍然是线性的，但现在我们有了这个不断增长的对象 seenGrids，根据我的直觉，它应该以二次方式扩展？我不知道如何证明或反驳它，当我运行 console.log(Object.keys(seenGrids).length) 用于 200x200 网格时，我得到 19900 既不是 m*n 也不是 m+n 那么它是线性的还是二次的？
时间 - O(n*m)？ - 这对我来说是最难理解的。它不应该再呈指数增长，因为由于保存了答案，很多子树都被跳过了，但我不知道如何以“正确”的方式推导时间复杂度。

Answer 1

第一个算法：

对于时间复杂度，最简单的证明就是你的方法！我的意思是递归函数的计算树。可以看到，展开时有一棵二叉树，树的最大长度为min(n,m)。因此，时间复杂度为 O(2^(min(m,n))).

对于 space 的复杂性，正如您所指出的，堆栈的计算将以深度优先的方式完成。因此，由于每个节点的最大分支为 2，树的最大长度为 min(m,n)（如前一段所述），space 复杂度将为 2 min(m,n).

第二种算法:

因为输入的最大不同组合是m * n（[1, 2, ..., m] 和 [1, 2, ..., n] 对于第一个和第二个输入函数，分别），堆栈调用的最坏情况在O(min(m, n))，space复杂度在O(m * n)，这是内存数组的大小。

对于时间复杂度，我们可以保证数组的每个元素都被计算一次（和记忆中的一样）。因此，独立于递归回调的复杂度，并且由于递归的深度优先计算（自下而上），第二种算法的时间复杂度为 O(m * n).

在仅向下或向右移动时，在 MxN 网格中从左上角到达右下角的方法数。什么是时间和 space 复杂度？

Number of ways to get from top left corner to bottom right corner in MxN grid while moving only down or right. What is time and space complexity?

javascript

algorithm

big-o

time-complexity

space-complexity