algorithm - 数学递归关系，用于计算最长公共(public)子序列的复杂度

我想用数学方法计算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));
}

有谁能解释如何驱动这种循环关系？

最佳答案

重复关系为：

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相等。