Se puede ver que tiene 2 bucles for, que serían O(n * m), sin embargo, en el bucle interior hay una búsqueda en amplitud.
Debido a que las islas se generan aleatoriamente, parece difícil cuantificar cuánto tiempo agregará esto.
/* 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());En el peor de los casos (que este tipo de prueba de complejidad suele verificar, cuando no se especifica lo contrario), el número de islas es directamente proporcional a la longitud y el ancho de la cuadrícula. Por ejemplo, con una cuadrícula de 4x4, podrías tener 8 islas:
xoxo oxox xoxo oxox Dicho esto, la cantidad de islas no es realmente un problema de complejidad aquí, creo, porque cada llamada de nivel superior de markIsland :
markIsland (para un total de no más de llamadas de length * width en todo el ciclo anidado) Entonces se puede decir que la complejidad general es O(n ^ 2) .
es O(N^2). El ciclo toma O(N^2). Luego, las búsquedas primero en amplitud cuentan cada 1 exactamente una vez, por lo que, en total, toman O (N ^ 2). Por lo tanto, el total es O(N^2) + O(N^2) = O(N^2).
Para problemas como este, no puede usar el cálculo de complejidad de tiempo simple de solo contar los bucles, porque el cuerpo de cada bucle podría ser potencialmente O (N ^ 2), lo que le da O (N ^ 4) como un límite superior , que es demasiado flojo.