遞歸算法的複雜性

我有一個算法，我想找出它的複雜性，但有遞歸，我不知道如何計算遞歸。我的代碼是：遞歸算法的複雜性

public boolean algorithm(int x, int y) { 
    if (x == matrixHeight - 1 && matrix1[x][y] == '0') { 
     return true; 
    } else if (x == 1 && matrix1[x-1][y] == '0') { 
     return true; 
    } else if (y == matrixWidth - 1 && matrix2[x][y] == '0') { 
     return true; 
    } else if (y == 1 && matrix2[x][y-1] == '0') { 
     return true; 
    } 
    if (matrix1[x-1][y] == '0' && tempMatrix[x-1][y] == '-'){ 
     path.push(new int[]{x-1, y}); 
     tempMatrix[x-1][y] = '+' 
     if (!algorithm(x-1, y)) { 
      path.pop(); 
     } else { 
      return true; 
     } 
    } 
    if (matrix2[x][y] == '0' && tempMatrix[x][y+1] == '-'){ 
     path.push(new int[]{x, y+1}); 
     tempMatrix[x][y+1] = '+'; 
     if (!algorithm(x, y+1)) { 
      path.pop(); 
     } else { 
      return true; 
     } 
    } 
    if (matrix1[x][y] == '0' && tempMatrix[x+1][y] == '-'){ 
     path.push(new int[]{x+1, y}); 
     tempMatrix[x+1][y] = '+'; 
     if (!algorithm(x+1, y)) { 
      path.pop(); 
     } else { 
      return true; 
     } 
    } 
    if (matrix2[x][y-1] == '0' && tempMatrix[x][y-1] == '-'){ 
     path.push(new int[]{x, y-1}); 
     tempMatrix[x][y-1] = '+'; 
     if (!algorithm(x, y-1)) { 
      path.pop(); 
     } else { 
      return true; 
     } 
    } 
    return false; 
}

在那裏，x，y在矩陣座標。
matrix1和matrix2是包含'0'或'1'
tempMatrix二維陣列由包含 '+' 或二維陣列 ' - '
path是堆棧
matrixHeight是matrix1.length
matrixWidth是matrix[0].length
N,M是矩陣的大小（constan t）

注意：這是使用回溯的迷宮解算器。

來源

2011-04-21 Martynas

此代碼需要註釋。 – Brad 2011-04-21 19:41:46

如果您可以簡要說明此代碼的作用以及如何執行此操作，那將會很有幫助。 – MAK 2011-04-21 19:57:03

此代碼不需要註釋，它只需要有意義的名稱。 – 2011-04-21 23:52:57

它看起來像一個深度第一迷宮解算器，如果您可以退出迷宮，則返回true，否則返回false。複雜性是O(lines * columns)，因爲在最壞的情況下你訪問每個單元的次數是固定的。

從（1,1）開始。你的算法會上升，回溯，向右，再試一次，回溯，再次右回溯，然後下降等等。對於像這樣構建的迷宮，它看起來像你的算法將花費大量的時間來解決它們。

事實上，大多數遞歸（深度優先更準確）方法將花費很長的時間，因爲它永遠是有可能迫使他們做的步驟的最大數量。

查看Lee algorithm以獲得更好的方法。

來源

2011-04-21 19:57:25 IVlad

是的你是對的。這是帶回溯的Maze算法。迷宮爲空時，複雜度爲O（行*列）。如果迷宮佔據特定數量的牆壁，那麼複雜程度如何？ – Martynas 2011-04-21 20:29:27

@Martynas - 不，如果迷宮空了，那是你最好的情況。在這種情況下，這是'O（n）'。對於特定數量的牆壁，我不確定是否容易分辨，如果您知道的話，它也不會幫助您。你應該假設它是'O（lines * columns）'。 – IVlad 2011-04-21 20:38:57

對於遞歸，您需要生成一個遞歸關係並求解。請參閱http://en.wikipedia.org/wiki/Recurrence_relation。沒有一種方法可以解決每一個復發關係，甚至從算法中產生一個復發關係。

一個例子是合併排序。考慮每次遞歸調用完成多少工作。首先，有一個恆定的時間劃分;然後進行兩次遞歸調用;那麼線性時間合併。遞歸調用需要多少工作？那麼，每個人都做同樣的事情，兩個遞歸調用加線性合併步驟。所以你需要表達樹的深度和寬度。您知道輸入大小爲n時，樹的高度爲O（log（n）），並且在每一步都完成了O（n）合併工作，因此O（n log（n））的工作是總計完成。

來源

2011-04-21 19:35:07

實際上這個算法的複雜性真的很簡單。

到algorithm每次調用使得零至四個遞歸調用algorithm和做其他工作一定一定量。所以，如果我們能約束的是algorithm被稱爲次數那麼我們就知道了複雜性。現在，請注意，在之前，每調用algorithm（除第一個外），您將tempMatrix的元素從' - '更改爲'+'。因此，調用算法的次數受tempMatrix大小限制，複雜度爲O(matrixWidth * matrixHeight)。

另一種方法（對於更多有意義的變量名會更明顯）只是注意到您正在x-y網格上進行深度優先搜索。所以每個「方」都會被訪問一次。

來源

2011-04-22 00:00:16

遞歸算法的複雜性

回答

相關問題