java - 迷宫寻路时递归DFS的时间和空间复杂度

Question

问题是:一个人正在二维数组中寻找目标(标记为 9)，其中 0 代表墙壁，1 代表道路。该方法应该确定该人是否可以找到目标。

我很容易使用 DFS 提出了解决方案，但在尝试找出代码的时间和空间复杂度时遇到了困难。

public boolean find(int[][] grid) {
    if(grid == null || grid.length == 0 || grid[0].length == 0 || grid[0][0] == 0) return 0;
    return helper(grid,0,0);    
}

private boolean helper(int[][] grid,int x, int y) {
    if(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
        if(grid[x][y] == 0) return false;
        else if(grid[x][y] == 9) return true;
        else if(grid[x][y] == 1) {
            grid[x][y]=2;
            return helper(grid,x,y-1) || helper(grid,x+1,y) || helper(grid,x,y+1) || helper(grid,x-1,y);
        }
        else return false;
    }
    else return false;
}

我认为时间和空间复杂度是O(mn)，但我不确定。

Answer 1

一般来说，DFS 的时间复杂度为 O(m + n)，空间复杂度为 O(n)，其中 n 是您可以位于的位置数，m 是位置之间的连接总数(如果您熟悉图论，则 n 是节点数，m 是边数)。在您的情况下，如果您有一个大小为 w × h 的网格，则 n = wh (每个网格位置可以有一个位置)并且 m ≤ 4wh (因为每个位置最多与其他四个位置相邻)。这意味着运行时间将为 O(wh)，空间复杂度也将为 O(wh)。