岛屿数量问题的时间复杂度

Question

我正在尝试解决以下问题：给定一个由0和1组成的网格，找出其中“岛屿”的数量，其中“岛屿”是指由上下左右移动可达到的一片连续的1区域。

下面给出的代码的时间复杂度是多少？我认为应该是O(rcn)，其中n是最大岛屿的大小。然而，在Geeks for Geeks上，他们说时间复杂度是O(V+E)。

void bfs(int r, int c, vector < vector < char >> & grid) {
  queue < pair < int, int >> q;
  int row[4] = {-1,0,1,0};
  int col[4] = {0,1,0,-1};
  q.push(make_pair(r, c));
  while (!q.empty()) {
    pair < int, int > p = q.front();
    int x = p.first;
    int y = p.second;
    q.pop();

    for (int i = 0; i < 4; i++) {
      if (x + row[i] < grid.size() && y + col[i] < grid[0].size() && x + row[i] >= 0 && y + col[i] >= 0 && grid[x + row[i]][y + col[i]] == '1') {
        q.push(make_pair(x + row[i], y + col[i]));
        grid[x + row[i]][y + col[i]] = '0';
      }
    }
  }
}
int numIslands(vector < vector < char >> & grid) {
  int count = 0;
  int r = grid.size();
  if (r == 0)
    return count;
  int c = grid[0].size();
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      if (grid[i][j] == '1') {
        bfs(i, j, grid);
        count++;
      }
    }
  }
  return count;
}

- Riyansh Pal

Answer 1

让我们从您的O(rcn)限制开始，其中

• r是行数，
• c是列数，
• n是最大岛屿大小。

我相信您是通过以下方式获得这个限制的：

1. 网格中总共有rc个位置。
2. 对于每个位置，我们可能需要在该位置上调用bfs函数。
3. bfs函数的工作量为O(n)。
4. 因此，总工作量为O(rcn)。

这种推理是正确的，但它会显著高估工作量。为了看到这一点，让我们考虑一个极端情况。假设整个网格都被填满了1。那么第一次调用bfs将会做大量的工作，但由于它将所有的1更改为0，将来的bfs调用将不会做任何重要的工作。具体来说，第一次调用bfs将做O(rc)的工作，因为它访问了网格中的每个位置，而所有将来的bfs调用只需要O(1)的时间。这使得总工作量为O(rc)，远低于O(rcn)的限制。

实际上，我们可以将在任何可能的输入情况下所做的工作量限制在O(rc)。以下是这样做的推理线索。如果我们忽略对bfs的调用，那么我们所做的基本工作量等于O(rc)，因为我们只访问每个网格位置一次。此外，在所有对bfs的调用中，每个网格位置最多可以从1变为0一次，而bfs函数所做的工作完全取决于有多少个1变成了0。网格中最多有rc个1，所以将所有这些1变成0所需的总工作量是O(rc)。因此，基本工作量是O(rc)，加上所有对bfs的调用所需的工作量最多也是O(rc)，所以我们总共需要O(rc)的工作量。

现在，当你在网上查找时，你得到了一个O(V + E)的界限。这个界限也是正确的，但要解释它的意思，我们需要知道V和E分别代表什么。在图搜索算法（如BFS）的上下文中，术语V指的是位置的数量（在图中称为节点），而E指的是位置之间的连接数（在图中称为边）。在你的情况下，节点的数量V是rc：每个网格单元格有一个节点。至于边，每对相邻的1值之间有一条边。因此，每个节点最多有4条与之相连的边（上/下/左/右），所以边的数量最多为4rc。这意味着O(V + E)的界限是O(rc + 4rc) = O(5rc) = O(rc)，其中的5被大O符号忽略了。这与我们之前得到的O(rc)相匹配，这意味着这是另一种完全正确的方法来得出结果。 :-)

- templatetypedef