algorithm - 求递归函数的时间复杂度

Question

作业是为了表明时间复杂度是 Ω(2 ^max(n,m) ) 在最坏的情况下跟随递归函数。

假设如下：

• n = w1len（单词 w1 的长度），
• m = w2len（单词 w2 的长度）

这是代码

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

    return res;
}

Answer 1

尝试为函数绘制调用树。它是什么样子的？你能估计 dist 函数的调用次数吗？