我正在努力计算这段代码中的时间复杂度。目前只能编写简单的代码...只想尝试复杂的代码！public static int PATHWAY = 0;public static int WALL = 1;public static int MARKED = 2;public static boolean find(int x, int y) { if(x == 7 && y == 7) return true; maze[x][y] = MARKED; if(x != 0 && maze[x-1][y] == PATHWAY && find(x-1, y)) return true; if(y != 0 && maze[x][y-1] == PATHWAY && find(x, y-1)) return true; if(x != 7 && maze[x+1][y] == PATHWAY && find(x+1, y)) return true; if(y != 7 && maze[x][y+1] == PATHWAY && find(x, y+1)) return true; return false;}
3 回答
慕沐林林
TA贡献2016条经验 获得超9个赞
好吧，在每个递归调用中，您都会访问 2D 数组中的单个单元格。
由于您标记了访问过的单元格，因此您不能两次访问同一单元格。
因此，总递归调用受二维数组的长度限制。
除了递归调用之外，您在方法的每次执行中执行恒定量的工作find()。
因此时间复杂度是O(N*M)ifN是二维数组的行数和M列数。
当然，根据 的停止条件if(x == 7 && y == 7) return true;，看起来您的二维数组的尺寸是 8x8，这可以看作是一个常量。这将使运行时间为 O(1)。
O(N*M)是一般输入数组的复杂度。
红糖糍粑
TA贡献1815条经验 获得超6个赞
基本上你可以计算分配和操作。有一个
int assignments = 0; int operations = 0;
每次执行此操作时都会增加该值。
另一种方法是监视时间，但这不是最可靠的方法。
您还可以计算/近似Big-O。
慕侠2389804
TA贡献1719条经验 获得超6个赞
嗯，这并不难，它实际上使用DFS来寻找路径。DFS 的阶数为O(V+E)，其中V是顶点数，E是边数。
在这种情况下，您使用邻接矩阵来表示您的图。因此，在最坏的情况下，时间复杂度将为O(M*N)，其中M是行数，N是列数。
添加回答
举报
0/150
提交
取消