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

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是列数。