证明递归算法的时间复杂度

我在赋值中给出了一个递归算法，其中我需要证明它具有给定的时间复杂度。证明递归算法的时间复杂度

的算法如下（用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（一个常数值）？对不起，如果问题是愚蠢的，只是从今天开始学习这些东西。 –

证明递归算法的时间复杂度

回答

相关问题