findIslands (leet代码)的大0时间复杂度是多少?

Question

可以看到它有2个for循环，这将是O(n * m)，然而，在内部循环中有一个广度优先搜索。

因为岛屿是随机生成的，所以很难量化这会增加多少时间。

/*
https://leetcode.com/problems/number-of-islands/
*/
const grid = [
[0, 1, 1, 0],
[0, 1, 1, 0],
[1, 0, 0, 0],
[1, 1, 0, 0],
];
function findIslands() {
let count = 0;
// traverse each row
for(let i = 0; i < grid.length; i++) {
// traverse each column in the row
for(let j = 0; j < grid[i].length; j++) {
if(grid[i][j]) {
count++;
markIsland(i, j);
}
}
}
return count;
}
function markIsland(i, j) {
// if either out of bounds or water(0) hit, do not recurse further
if( i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] === 0 ) {
return;
}
// mark the entire island as water to avoid recursing it again
grid[i][j] = 0;
// recurse in all 4 directions
markIsland(i-1, j);     //  up
markIsland(i,   j+1);   //  right
markIsland(i+1, j);     //  down
markIsland(i,   j-1);   //  left
}
console.log(findIslands());

Answer 1

等于0 (N^2)。这个循环耗时O(N²)然后广度优先搜索每个1只算一次，所以总共要花O(N²)因此，总数为O(N^2) + O(N^2) = O(N^2)。

对于这样的问题，你不能使用简单的时间复杂度计算，只计算循环，因为每个循环的主体可能是O(N^2)，这会给你O(N^4)作为上界，这太宽松了。

Answer 2

最坏情况(当没有特别说明时，这种复杂性测试通常会检查这种情况)，岛屿的数量与网格的长度和宽度成正比。例如，在4x4网格中，您可以有8个岛屿:

xoxo
oxox
xoxo
oxox

也就是说，岛屿的数量在这里并不是一个真正的复杂性问题，我认为，因为markIsland的每个顶级调用将要么:

• 在发现0时立即终止，或者
• 递归调用markIsland(在整个嵌套循环中总共不超过length * width调用)

所以总的复杂度可以说是O(n ^ 2)。