再帰アルゴリズムの時間複雑度を証明する

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; 

}

割り当ては、このアルゴリズムが実際の時間複雑オメガ（2 ^最大（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つの項であると考える。その後、数式を2〜3段階に拡大して一般化するだけです。私はその後、私の上記の時間の複雑さで終わる。私は時間の複雑さがどのように2 ^（max（n、m））になるか分かりません。なぜなら、メソッドごとに3つの追加の再帰呼び出しがあるからです。 2つの長さのうちの1つがゼロであるとき、線形（右？）。

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" 

単一のコールが3間接呼び出しを必要とするように、2つのパワーを持つソリューションは、ほとんどありませんが従わなければなりません。