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

Question

我在作业中得到了一个递归算法，我需要证明它具有给定的时间复杂度。

算法如下(用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;

赋值是为了证明这个算法确实有时间复杂度Omega(2^max(n, m)) 其中n和m分别是w1和w2的长度。至少可以说我在这方面的知识很少，但我设法找到了 video on youtube分析斐波那契数列递归很有帮助。

我基本上已经尝试根据我的算法对视频中的解决方案进行反向工程，但我最终得到了时间复杂度 Omega(3^min(n, m))。

我得出这个结论的方式(我确信这绝不是正确的方式)是我通过说 T(n-1, m -1) = T(m, n-1) 和 T(m-1, n)(因为我认为这是其他两项)。之后，我只是将公式扩展两到三个步骤并将其概括。然后我以上述时间复杂度结束。我不明白时间复杂度怎么会是 2^(max(n,m))，因为每个调用都有 3 个额外的递归调用，而且我也不明白为什么它是最大值而不是最小值，因为方法是线性(对吗？)当两个长度之一为零时。

Answer 1

运行时间必须跟随递归

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"

不太可能采用 2 的幂的解决方案，因为单个调用涉及三个间接调用。