图 (O(V+E)) 上 DFS 与矩阵 (3^(M*N)) 上 DFS 的时间复杂度

Question

如果听起来太不合逻辑，我们深表歉意。

今天在做一些竞赛题的时候，一个奇怪的想法闪过我的脑海。

我们说 DFS 的时间复杂度是 O(V+E)，因为我们只遍历邻接表一次，即对于每个节点我们都考虑它的边。

然而，当对大小为 MN 的矩阵执行 dfs 时。我们可以说一个矩阵是一个有 MN 个顶点的图（每个单元格都是一个顶点）并且它的相邻单元格有一条边 ==> 每个顶点都有 4 条边（为简单起见，忽略边界情况）

然后在我们做 DFS 的时候

    private void dfs(int grid[][], int i, int j, int m, int n) {
        if(i<0 || j<0 || i>m || j>n || visited[i][j])
            return;
        visited[i][j] = true;
        dfs(grid, i+1, j, m, n);
        dfs(grid, i-1, j, m, n);
        dfs(grid, i, j-1, m, n);
        dfs(grid, i, j+1, m, n)
        visited[i][j] = false;
    }

==> 在图形术语中它的 O(V+E) => O(MN + 4MN) => O(5MN) => O(MN) ==> 但是时间复杂度是 4^(MN)

这个类比哪里错了？

Answer 1

O(V+E) 的复杂度只有在每个节点被访问一次时才成立。在您的代码中，您访问了一个节点并将其标记为已访问，但在 parent 完成后，您将其标记为未访问。

所以当处理下一个child时，它会再次访问它的parent。如果 parent 有 4 children 它将被它的 children 额外访问 1 次，使每个节点访问 4 次，复杂度为 4x4x...(MN) = 4 ^MN.

你删除visited[i][j] = false，你会看到一个节点一旦访问过就再也不会访问了，复杂度是 O(节点数) = O(MN)

图 (O(V+E)) 上 DFS 与矩阵 (3^(M*N)) 上 DFS 的时间复杂度

Time complexity of DFS on graph (O(V+E)) vs DFS on matrix (3^(M*N))

algorithm

backtracking

time-complexity

depth-first-search