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

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 的幂的解决方案，因为单个调用涉及三个间接调用。

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

Prove time complexity of recursive algorithm

java

algorithm

recursion

big-o

time-complexity