矩阵中最长递增路径中 DFS 的时间复杂度

Question

我遇到了在矩阵中寻找最长递增路径的问题。蛮力解决方案非常简单：

public class Solution {

  private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  private int m, n;

  public int longestIncreasingPath(int[][] matrix) {
      if (matrix.length == 0) return 0;
      m = matrix.length;
      n = matrix[0].length;
      int ans = 0;
      for (int i = 0; i < m; ++i)
          for (int j = 0; j < n; ++j)
              ans = Math.max(ans, dfs(matrix, i, j));
      return ans;
  }

  private int dfs(int[][] matrix, int i, int j) {
      int ans = 0;
      for (int[] d : dirs) {
          int x = i + d[0], y = j + d[1];
          if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
              ans = Math.max(ans, dfs(matrix, x, y));
      }
      return ++ans;
  }
}

时间复杂度为 O(2^(m+n))，其中 m 为否。行数，n 是第几行。矩阵中的列数。

我很难理解这一点。第一个嵌套的 for 循环是 O(mn)，这很好。现在每个单元格都被视为根，并对其进行 DFS。但是DFS的时间复杂度是O(V + E)，这里是V = mn and E = 4*mn，所以每个dfs应该是O(mn)，所以总的时间复杂度应该是O(mn) x O(mn) = O(m^2.n^2)对吧？

注意：我知道这不是最佳解决方案，可以记忆，但是我的问题是关于理解这种粗暴的方法的时间复杂度。

Answer 1

你的 DFS 不是 O(V+E) = O(nm) 因为你没有访问集。如果没有这个集合，您的各个分支采用的路径可能会重叠和重复工作，这样您就可以从 longestIncreasingPath 的任何给定 DFS 调用中多次探索相同的顶点并遍历相同的边。分支因子为 4 的无记忆搜索是导致指数行为的原因。

例如，考虑完美凸矩阵的潜在最坏情况：

6 5 4 3 4 5 6
5 4 3 2 3 4 5
4 3 2 1 2 3 4 
3 2 1 0 1 2 3
4 3 2 1 2 3 4
5 4 3 2 3 4 5
6 5 4 3 4 5 6

您搜索的任何顶点的最坏情况路径是沿对角线爬升到最近的角，这样的路径是 O((n+m)/2) 步长。每个顶点最多有 4 个选项，并且由于在递归调用之间没有以访问集形式存在的共享内存，因此您会得到一个天真的 4^((n+m)/2) = 2^(n+m) 最差- DFS 的案例复杂度。更准确地说，在这种最坏情况下，大多数顶点只有 2 到 3 个可行的邻居可以递归，这样每次搜索的实际最坏情况复杂度将介于 sqrt(2)^(n+m) 之间和 sqrt(3)^(n+m)，但指数运行-time 是相同的。

如果你有一个访问集，你会得到一个更像你在答案中提到的那样的复杂性。这将是 O(nm*((n+m)/2)) = O(n^2*m + m^2*n) 因为路径增加的限制，但没有该限制它将是 O( (纳米)^2).

矩阵中最长递增路径中 DFS 的时间复杂度

Time Complexity of DFS in logest increasing path in a matrix

java

time-complexity

depth-first-search