我正在努力計(jì)算這段代碼中的時(shí)間復(fù)雜度。目前只能編寫簡單的代碼...只想嘗試復(fù)雜的代碼！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貢獻(xiàn)2016條經(jīng)驗(yàn) 獲得超9個(gè)贊
好吧，在每個(gè)遞歸調(diào)用中，您都會(huì)訪問 2D 數(shù)組中的單個(gè)單元格。
由于您標(biāo)記了訪問過的單元格，因此您不能兩次訪問同一單元格。
因此，總遞歸調(diào)用受二維數(shù)組的長度限制。
除了遞歸調(diào)用之外，您在方法的每次執(zhí)行中執(zhí)行恒定量的工作find()。
因此時(shí)間復(fù)雜度是O(N*M)ifN是二維數(shù)組的行數(shù)和M列數(shù)。
當(dāng)然，根據(jù) 的停止條件if(x == 7 && y == 7) return true;，看起來您的二維數(shù)組的尺寸是 8x8，這可以看作是一個(gè)常量。這將使運(yùn)行時(shí)間為 O(1)。
O(N*M)是一般輸入數(shù)組的復(fù)雜度。
紅糖糍粑
TA貢獻(xiàn)1815條經(jīng)驗(yàn) 獲得超6個(gè)贊
基本上你可以計(jì)算分配和操作。有一個(gè)
int?assignments?=?0; int?operations?=?0;
每次執(zhí)行此操作時(shí)都會(huì)增加該值。
另一種方法是監(jiān)視時(shí)間，但這不是最可靠的方法。
您還可以計(jì)算/近似Big-O。
慕俠2389804
TA貢獻(xiàn)1719條經(jīng)驗(yàn) 獲得超6個(gè)贊
嗯，這并不難，它實(shí)際上使用DFS來尋找路徑。DFS 的階數(shù)為O(V+E)，其中V是頂點(diǎn)數(shù)，E是邊數(shù)。
在這種情況下，您使用鄰接矩陣來表示您的圖。因此，在最壞的情況下，時(shí)間復(fù)雜度將為O(M*N)，其中M是行數(shù)，N是列數(shù)。
添加回答
舉報(bào)
0/150
提交
取消