这两个程序的时间复杂度是多少

Question

有人能向我解释这三种方法的时间复杂性，并帮助我理解为什么会有这种时间复杂性吗。这两种方法都采用一个矩阵，并找到它周围的所有邻居。第一种方法通过递归完成，第二种方法通过迭代和堆栈完成，第三种方法通过尾部递归完成。

这里是第一种方法：

public static int ExploreAndLabelColony(char[][] grid, int i, int j, char c) { 
grid[i][j] = c;
int count = 1;

if ((i>0 && i<grid.length && j<grid[0].length) && (grid[i-1][j] == '1')) { //vertical top
count += ExploreAndLabelColony(grid, i-1,j,c); 
}
if (i+1<grid.length && j<grid[0].length && grid[i+1][j] == '1') { //vertical bottom
count +=ExploreAndLabelColony(grid, i+1,j,c); 
}
if (j>0 && i<grid.length && j<grid[0].length && grid[i][j-1] == '1') { //horizontal left
count +=ExploreAndLabelColony(grid, i,j-1,c); 
}
if (i<grid.length && j+1<grid[0].length && grid[i][j+1] == '1') { //horizontal right
count +=ExploreAndLabelColony(grid, i,j+1,c); 
}
if (i+1<grid.length && j+1<grid[0].length && grid[i+1][j+1] == '1') { //diagonal bottom right
count +=ExploreAndLabelColony(grid, i+1,j+1,c);
} 
if (j>0 && i+1<grid.length && j<grid[0].length && grid[i+1][j-1] == '1') { //diagonal bottom left
count +=ExploreAndLabelColony(grid, i+1,j-1,c);
} 
if (i>0 && i<grid.length && j+1<grid[0].length && grid[i-1][j+1] == '1') { //diagonal top right
count += ExploreAndLabelColony(grid, i-1,j+1,c);
} 
if (i>0 && j>0 && i<grid.length && j<grid[0].length && grid[i-1][j-1] == '1') { //diagonal top left
count +=ExploreAndLabelColony(grid, i-1,j-1,c);
}

return count;
}
}

这是第二种方法：

public static int ExploreAndLabelColony(char[][] grid, int i, int j, char c) { 
Stack<String> strStack = new Stack<>();
strStack.push(i + "," + j);
while (!strStack.empty()) {
String x = strStack.pop();

int row = Integer.parseInt(x.split(",")[0]);
int col = Integer.parseInt(x.split(",")[1]);
if(row<0 || col<0 || row>=grid.length || col>=grid[0].length || visited[row][col] || grid[row][col]!='1')
continue;

visited[row][col]=true;
grid[row][col]=c;
count++;
strStack.push(row + "," + (col-1)); //left
strStack.push(row + "," + (col+1)); //right
strStack.push((row-1) + "," + col); //up
strStack.push((row+1) + "," + col); //down
strStack.push((row-1) + "," + (col-1)); //left & up
strStack.push((row-1) + "," + (col+1)); //right & up
strStack.push((row+1) + "," + (col-1)); //left & down
strStack.push((row+1) + "," + (col+1)); //right & down  
}    
return count;
}

这是第三种方法：

static int ExploreAndLabelColony(Point point, char[][] grid, char c, int count) {
if (point == null) {
return count; // no more work
}
int i = point.i;
int j = point.j;
point = point.next;
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {

} else if (grid[i][j] != '1') {

} else {
grid[i][j] = c;  // label
count++;
point = new Point(i - 1, j - 1, point);
point = new Point(i - 1, j, point);
point = new Point(i - 1, j + 1, point);
point = new Point(i, j - 1, point);
point = new Point(i, j + 1, point);
point = new Point(i + 1, j - 1, point);
point = new Point(i + 1, j, point);
point = new Point(i + 1, j + 1, point);
}
return ExploreAndLabelColony(point, grid, c, count);
} 

Answer 1

给定n行和m列，两者的时间复杂度都应该是O(mn(。由于您是通过引用传递网格，而不是重新访问访问的单元格，因此这是深度优先搜索。第二个方法与第一个方法相同，但将第一个方法中的调用堆栈替换为自己的堆栈。