gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-30 03:09:18 26 4
gpt4 key购买 nike

问题是:一个人正在二维数组中寻找目标(标记为 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),但我不确定。

最佳答案

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

关于java - 迷宫寻路时递归DFS的时间和空间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33966965/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com