如何计算这段代码的时间复杂度？

Question

我正在努力计算这段代码中的时间复杂度。目前只能编写简单的代码...只想尝试复杂的代码！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;}

Answer 1

好吧，在每个递归调用中，您都会访问 2D 数组中的单个单元格。

由于您标记了访问过的单元格，因此您不能两次访问同一单元格。

因此，总递归调用受二维数组的长度限制。

除了递归调用之外，您在方法的每次执行中执行恒定量的工作find()。

因此时间复杂度是O(N*M)ifN是二维数组的行数和M列数。

当然，根据 的停止条件if(x == 7 && y == 7) return true;，看起来您的二维数组的尺寸是 8x8，这可以看作是一个常量。这将使运行时间为 O(1)。

O(N*M)是一般输入数组的复杂度。

Answer 2

基本上你可以计算分配和操作。有一个

int assignments = 0;
int operations = 0;

每次执行此操作时都会增加该值。

另一种方法是监视时间，但这不是最可靠的方法。

您还可以计算/近似Big-O。

Answer 3

嗯，这并不难，它实际上使用DFS来寻找路径。DFS 的阶数为O(V+E)，其中V是顶点数，E是边数。

在这种情况下，您使用邻接矩阵来表示您的图。因此，在最坏的情况下，时间复杂度将为O(M*N)，其中M是行数，N是列数。