Findislands（LEET代码）的时间复杂性是什么？
可以看到它有2个用于循环的循环，但是，在内部环中，有一个广度的搜索。
由于这些岛屿是随机生成的，因此似乎很难量化这将增加多少时间。
/*
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());
One can see that it has 2 for loops, which would be O(n * m), however, in the inner loop there is a breadth first search.
Because the islands are randomly generated, it seems difficult to quantify how much time this will add.
/*
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());
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是O（n^2）。循环为O（n^2）。然后，广度首先搜索每1次计数，因此总共将O（n^2）占据。因此，总计为o（n^2） + o（n^2）= o（n^2）。
对于此类问题，您不能使用仅计算循环的简单时间复杂性计算，因为每个循环的主体可能是O（n^2），它可以使您o（n^4）作为上限，太松了。
It is O(N^2). The loop takes O(N^2). Then the breadth first searches count each 1 exactly one time, so in total, they take O(N^2). Thus, the total is O(N^2) + O(N^2) = O(N^2).
For problems like this, you can't use the simple time complexity calculation of just counting the loops, because the body of each loop could potentially be O(N^2), which gives you O(N^4) as a upper bound, which is too loose.
最糟糕的案例（这种复杂性测试通常是在未指定的情况下检查的），岛屿的数量与网格的长度和宽度成正比。例如，有了4x4网格，您可以拥有8个岛屿：
也就是说，我认为，这里的岛屿数量并不是真正复杂性的问题要么：
Markisland（总共不超过长度 *宽度 *宽度在整个嵌套环上调用），因此总体复杂性可以说是
o（n ^ 2）。Worst-case (which this sort of complexity test is usually checking, when not otherwise specified), the number of islands is directly proportional to the length and width of the grid. For example, with a 4x4 grid, you could have 8 islands:
That said, the number of islands isn't really an issue for complexity here, I think, because each top-level call of
markIslandwill either:markIsland(for a total of no more thanlength * widthcalls over the entire nested loop)So the overall complexity can be said to be
O(n ^ 2).