岛屿数量问题迭代DFS解法的时间复杂度疑问

问题背景 #

这是LeetCode上的岛屿数量问题，要求找出矩阵中代表岛屿的“1”的数量。以下是迭代深度优先搜索（DFS）的解决方案：

public int numIslands(char[][] grid) {
    Stack<Integer> stack = new Stack<>();
    int counter = 0;
    int northBound = 0;
    int eastBound = grid[0].length - 1;
    int southBound = grid.length - 1;
    int westBound = 0;
    
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                stack.add(i);
                stack.add(j);
                counter += 1;

                while (stack.size() > 0) {
                    int y = (int) stack.pop();
                    int x = (int) stack.pop();
                    grid[x][y] = '0';

                    if (x-1 >= northBound && grid[x-1][y] == '1') {
                        stack.push(x-1);
                        stack.push(y);
                    }

                    if (y+1 <= eastBound && grid[x][y+1] == '1') {
                        stack.push(x);
                        stack.push(y+1);
                    }

                    if (x+1 <= southBound && grid[x+1][y] == '1') {
                        stack.push(x+1);
                        stack.push(y);
                    }

                    if (y-1 >= westBound && grid[x][y-1] == '1') {
                        stack.push(x);
                        stack.push(y-1);
                    }
                }
            }
        }
    }

    return counter;
}

疑问 #

多数人采用递归解法，普遍认为该问题DFS解法的时间复杂度为O(m * n)（其中m为矩阵行数，n为列数）。但我分析自己的迭代解法时认为时间复杂度是O((m * n)^2)：外层两层for循环遍历每个元素，复杂度为O(m * n)，而每个元素触发的内层while循环可能访问1到mn个元素，因此总复杂度应为O((mn)(mn))。想请教我的复杂度分析错误之处，以及为何他人忽略内层while循环的复杂度？

解答 #

你的复杂度分析错误在于重复计算了元素的访问次数。

• 外层循环遍历每个元素时，只有当元素是'1'的时候才会进入while循环处理，而一旦处理这个元素，我们会立刻把它设为'0'（grid[x][y] = '0'），这意味着这个元素后续不会再被任何循环（外层for或内层while）访问到。
• 整个算法中，每个矩阵元素最多被访问两次：一次是外层for循环检查它是否为'1'，另一次是内层while循环中被弹出栈、标记为'0'并处理其相邻元素。
• 不管是外层for还是内层while，所有操作的总次数都是和矩阵元素总数m*n成正比的，没有嵌套的二次方级别的重复操作。

举个简单例子：如果整个矩阵全是'1'，外层循环只会在第一个元素(i=0,j=0)触发while循环，这个while循环会把所有元素都标记为'0'，后续的外层for循环遍历到其他元素时，因为已经是'0'，不会再进入while循环。总操作次数就是mn级别，而不是(mn)^2。

其他人没有忽略内层while循环的复杂度，而是意识到内层while循环的总执行次数是和外层循环的有效触发次数加起来线性于m*n的，两者不是独立的嵌套关系，而是互补的——处理过的元素不会再被重复处理，所以整体复杂度是O(m*n)。

内容的提问来源于stack exchange，提问作者Stacking_Flow