0

LCSアルゴリズム問題の漸化式を数学的に計算したいと思います。私の目的は、マスターの定理を適用して複雑度O（2 ^ n）を計算することです。

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
   if (m == 0 || n == 0)
     return 0;
   if(X[m-1] == Y[n-1])
     return 1 + lcs(X, Y, m-1, n-1);
   else
     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

誰でもその漸化式を推進する方法を説明できますか？

4

1 に答える 1

1

再帰関係は次のようになります。

T(n,m) = T(n-1,m-1)+O(1), if (X[m-1] = Y[n-1])
         or
         T(n-1,m)+T(n,m-1)+O(1), otherwise

次のような最悪のシナリオを考慮する必要があります。

 T(n,m) = T(n-1,m)+T(n,m-1)+O(1)

全体を通して。要約すると、次のようになります。

T(n,m) <= 2^(n-1) T(0,m) + ... , if m<n (longest branch of height n)
         or
         2^(m-1) T(n,0) + ... , if n<m (longest branch of height m)

ここで、最長の枝の長さが k である場合、他のすべての枝も同様に高さ k であると仮定すると、上限が得られます。T(0,k) と T(k,0) はどちらも定数なので、

T(n,m) = O(2^(max(n,m)))

または

T(n,m) = O(2^n)

n と m が等しい場合。

于 2013-03-08T10:07:58.410 に答える