我正在努力計算這段代碼中的時間復雜度。目前只能編寫簡單的代碼...只想嘗試復雜的代碼！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
提交
取消