如何確定此代碼的時間複雜度？

我剛開始學習算法，如何確定此代碼的時間複雜度？

int findMinPath(vector<vector<int> > &V, int r, int c){ 
    int R = V.size(); 
    int C = V[0].size(); 
    if (r >= R || c >= C) return 100000000; // Infinity 
    if (r == R - 1 && c == C - 1) return 0; 
    return V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1)); 
}

我想答案應該爲O（R C），但正確的答案是O（2 ^（R C））我不明白爲什麼。請解釋。

來源

2017-02-09 Manasvini Ganesh

它是雙重遞歸的。如果將呼叫映射爲圖形，則會得到一個二進制呼叫樹。算法雖然對我沒有意義。 –

嗯。是不是O（（C + R）選擇C），因爲代碼基本上是枚舉從（0,0）到（C，R）的路徑。？我認爲這是O（2 ^（RC）），但這是一個非常糟糕的上限。例如，當R = C時，（C + R）選擇C約爲4^R/sqrt（pi * R），其增長速度比2 ^（R^2）慢得多。 –

也許在問題中有一個錯字：O（2 ^（R + C））而不是O（2 ^（RC））？搜索樹的深度至多是R + C，所以2 ^（R + C）是對複雜度的合理的第一近似。當然R + C = O（RC），所以現在的問題在理論上也是正確的，但對我來說沒有多大實際意義（至少對我而言）。 –

當你有多個遞歸調用時，一個好的近似值是分支（調用）的數量增加到「樹」的高度。

你的情況，你有兩個分支：

findMinPath(V, r+1, c) 
findMinPath(V, r, c+1)

因此，我們將用2

然後高度（或深度）基地開始你的「樹」被確定向量中有多少個元素;在你的情況下，你有R個元素，但是每個元素都有C元素。所以我們的力量是RC。

因此，您的運行時間將近似，在最壞的情況下爲O（2^RC）。

來源

2017-02-09 16:01:47 Cruiser

樹的最大深度是R + C而不是RC，不是嗎？從（R，C）開始的距離是R + C，每次遞歸調用距離減1。 –

@PaulHankin我認爲這是因爲在最壞的情況下R * C的所有元素都將被遍歷，所以Cruiser解釋說，它應該是2 ^（R * C） –

在最壞的情況下，在單一路徑中，R + C（或也許是R + C-2，但這對複雜性沒有影響），遍歷元素，而不是RC元素。矢量中有RC元素，但網格中搜索路徑的步驟僅在方向（+1,0）和（0，+1）處進行。 –

最壞的情況下，findMinPath調用本身兩次在這一行

return V[r][c] + min(findMinPath(V, r + 1, c), findMinPath(V, r, c + 1));

因此，最壞的情況下，每一個通話將直到遞歸結束涉及另外兩個電話。因此，兩個權力。

來源

2017-02-09 16:01:12 doctorlove

爲什麼2 ^（RC）不是，例如2 ^（R + C）。由於R + C是搜索樹的最大深度。 –

如何確定此代碼的時間複雜度？

回答

相關問題