Leetcode上“岛屿数量”的DFS和BFS时空复杂性

Question

这是问题描述。建议的前两个解决方案涉及DFS和BFS。这个问题涉及第一种方法：DFS和BFS。

我将问题陈述包括在此处，以便于阅读。

Given a 2d grid map of '1's (land) and '0's (water), count the number of 
islands. An island is surrounded by water and is formed by connecting adjacent
lands horizontally or vertically. You may assume all four edges of the grid are 
all surrounded by water.

    Example 1:

    Input:
    11110
    11010
    11000
    00000

    Output: 1


    Example 2:

    Input:
    11000
    11000
    00100
    00011

    Output: 3

对于DFS和BFS的时间复杂度为何同时存在，我不清楚O(rows * columns)。我看到网格只是充满0的情况是怎么回事-我们只需要检查每个单元格即可。但是，DFS方法是否不会增加搜索时间？即使我们通过0在dfs方法中将访问的单元格标记为来标记它们，由于两个外部循环，我们仍然会重新访问所有单元格。如果在行数和列数较大的大网格中dfs的时间复杂度为O（n），那么时间复杂度不是O（行*列* max [rows，cols]）吗？此外，是不一样的情况下，与BFS方法，即它是O(rows * cols * possibleMaxSizeOfQueue)在那里possibleMaxSizeOfQueue可以再次max[rows, cols]？

for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }

DFS的空间复杂度O(rows*cols)如何？当递归分支返回时，是否不可能/通常认为调用堆栈空间已释放？BFS的空间复杂度如何O(min(rows, cols))？从我的角度来看，在只有1的网格的情况下，队列中可能充满了所有元素，从而降低O(rows*cols)了BFS空间的复杂性。

DFS解决方案

class Solution {
  void dfs(char[][] grid, int r, int c) {
    int nr = grid.length;
    int nc = grid[0].length;

    if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
      return;
    }

    grid[r][c] = '0';
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
  }

  public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
      return 0;
    }

    int nr = grid.length;
    int nc = grid[0].length;
    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }

    return num_islands;
  }
}

时间复杂度：O（M×N），其中M是行数，N是列数。

空间复杂度：最糟糕的情况是O（M×N），如果网格图填充了DFS深达M×N的陆地。

BFS解决方案

class Solution {
  public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
      return 0;
    }

    int nr = grid.length;
    int nc = grid[0].length;
    int num_islands = 0;

    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          grid[r][c] = '0'; // mark as visited
          Queue<Integer> neighbors = new LinkedList<>();
          neighbors.add(r * nc + c);
          while (!neighbors.isEmpty()) {
            int id = neighbors.remove();
            int row = id / nc;
            int col = id % nc;
            if (row - 1 >= 0 && grid[row-1][col] == '1') {
              neighbors.add((row-1) * nc + col);
              grid[row-1][col] = '0';
            }
            if (row + 1 < nr && grid[row+1][col] == '1') {
              neighbors.add((row+1) * nc + col);
              grid[row+1][col] = '0';
            }
            if (col - 1 >= 0 && grid[row][col-1] == '1') {
              neighbors.add(row * nc + col-1);
              grid[row][col-1] = '0';
            }
            if (col + 1 < nc && grid[row][col+1] == '1') {
              neighbors.add(row * nc + col+1);
              grid[row][col+1] = '0';
            }
          }
        }
      }
    }

    return num_islands;
  }
}

时间复杂度：O（M×N），其中M是行数，N是列数。

空间复杂度：O（min（M，N）），因为在最坏的情况下，网格充满了陆地，队列的大小可能会增长到min（M，N）。

Answer 1

DFS的时间复杂度与访问的图的顶点和边的总数成比例。在那种情况下，有N*M顶点并且比4*N*M边缘稍少，它们的和仍为O(N*M)。

为什么这样：因为我们在每个方向上只一次处理每个边缘。递归呼叫立即终止的情况无关紧要，因为可以在呼叫站点上计算该呼叫所花费的时间；因此，每个定向边最多只能调用一次O(N*M)。

BFS的时间复杂度非常相似。队列的最大长度完全无关紧要，因为我们根本不会对队列进行整体检查。队列仅获得“追加”和“先删除”查询，无论队列大小如何，都可以在固定时间内进行处理。如果我们需要检查顶点是否已被访问，则可以在固定时间内进行。

DFS的最坏情况的空间复杂度是Theta(N*M)：只需采用任何“蛇形”迷宫：

......
#####.
......
.#####
......

在这里，DFS将被迫遍历整个路径，然后再停止并开始释放堆栈。但是，在任何情况下N*M+1，堆栈上的元素都不会超过。

BFS的最坏情况的空间复杂度确实不是O(max(N, M))：Theta(N*M)甚至当我们正在考虑简单网格时。这是math.stackexchange.com的示例：

如果我们从红点开始BFS，它将以一个队列结尾，该队列包含树的所有叶子，它们的数量与成正比N*M。您也可以截断示例的3/4，并使红点出现在左上角。

就BFS的最坏情况下的内存消耗而言，您似乎已读过的解决方案是错误的。