證明遞歸算法的時間複雜度

我在賦值中給出了一個遞歸算法，其中我需要證明它具有給定的時間複雜度。證明遞歸算法的時間複雜度

的算法如下（用Java編寫的）

int partDist(String w1, String w2, int w1len, int w2len) { 
    if (w1len == 0) 
     return w2len; 
    if (w2len == 0) 
     return w1len; 
    int res = partDist(w1, w2, w1len - 1, w2len - 1) + 
    (w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1); 
    int addLetter = partDist(w1, w2, w1len - 1, w2len) + 1; 
    if (addLetter < res) 
     res = addLetter; 
    int deleteLetter = partDist(w1, w2, w1len, w2len - 1) + 1; 
    if (deleteLetter < res) 
     res = deleteLetter; 
    return res;

}

的任務是證明，該算法確實有足夠的時間複雜度歐米茄（2^MAX（N，M））其中n和m分別是w1和w2的長度。我在這方面的知識很少，但我已經設法找到video on youtube分析Fibonacci序列遞歸很有幫助。

我已經基本上嘗試了從我的算法視頻解決方案的後向工程，但最終的時間複雜性歐米茄（3^min（n，m））。

我得出這個結論的方式，我決定不是正確的方法，我計算一種下界（我猜？），說T（n-1， m-1）= T（m，n-1）和T（m-1，n）（因爲我認爲這些是另外兩個術語）。之後，我只是擴展公式兩個或三個步驟，並概括它。然後我以上述時間複雜性結束。我不明白時間複雜度如何可以是2 ^（max（n，m）），因爲每個人都有3個額外的遞歸調用，我不明白爲什麼它是最大值而不是最小值，因爲方法是線性（右？），當兩個長度之一爲零時。

來源

2017-01-26 Nyfiken Gul

的運行時間必須按照復發

T(n, m) = T(n - 1, m - 1) + T(n, m - 1) + T(n - 1, m) + T 
T(0, m) = T' 
T(n, 0) = T"

有兩個電源解決方案是不可能的，因爲單個呼叫涉及三個間接調用。

來源

2017-01-26 13:59:55

感謝您的回答，這就是我的想法！ T'和T''符號是什麼？而第一行的T等於只是說C（一個常數值）？對不起，如果問題是愚蠢的，只是從今天開始學習這些東西。 –

證明遞歸算法的時間複雜度

回答

相關問題