我如何计算此代码的时间复杂度？

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

基本上你可以计算赋值和操作。有一个

int assignments = 0;
int operations = 0;

每做一次就会递增。

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

你也可以calculate/approximate大O，勾选Big O, how do you calculate/approximate it?

Answer 2

嗯，在每个递归调用中，您访问二维数组中的单个单元格。

由于标记了访问过的单元格，所以不能访问同一个单元格两次。

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

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

因此，如果 N 是二维数组的行数，M 是二维数组的列数，那么时间复杂度是 O(N*M)。

当然，根据你if(x == 7 && y == 7) return true;的停止条件，你的二维数组的维度好像是8x8，可以看成一个常数。这将使运行时间为 O(1)。

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

Answer 3

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

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

我如何计算此代码的时间复杂度？

How do I calculate this code's time complexity?

java

time

complexity-theory