C/C++教程

LCS算法及其时空优化

本文主要是介绍LCS算法及其时空优化,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

经典算法

求解\(LCS\)(最长公共子序列)时,一般采用动态规划的方法。

例:有\(strn\)与\(strm\)两个序列,设\(DP\)方程\(f[i][j]\)表示\(strn\)的前\(i\)位与\(strm\)的前\(j\)位的LCS长度,转移方程如下:$$strn[i]==strm[j]:f[i][j]=f[i-1][j-1] +1$$

\[strn[i]!=strm[j]:f[i][j]=max(f[i][j-1],f[i-1][j]) \]

注意:上述两者可以相互独立,即当两字符相等的时候只进行第一步即可。

证明:\(f[i-1][j-1]+1>=max(f[i][j-1],f[i-1][j])\)必定成立。

时间复杂度:\(O(nm)\)
空间复杂度:\(O(nm)\)

for( int i = 0; i < len_n; i++ )
{
    for( int j = 0; j < len_m; j++)
    {
        if(strn[i] == strm[j])
        {
            f[i][j] = f[i-1][j-1] + 1; 
        }
        else 
        {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
        }
    }
}

空间复杂度优化

注意到转移时只与\(f[i-1][j-1]、f[i-1][j]、f[i][j-1]\)有关,因此可以尝试滚动数组优化。

设\(dp[j]\)代表当前循环到\(strn\)的第\(i\)个字符时的答案构成的数组。
在更新\(dp[j]\)时,即是对应经典算法中的\(dp[i][j]\),则此时\(dp[j]\)中保留的数据应该是\(dp[i-1][j]\),而\(dp[j-1]\)保留的数据是\(dp[i][j-1]\)。
那么应该如何获得\(dp[i-1][j-1]\)呢?
可以开一个临时变量\(temp\),保留每一次更新前的\(dp[j]\)(相当于\(dp[i-1][j]\)),则当循环进行到第\(j+1\)个字符时,\(temp\)内保留的数据就相当于我们要求的\(dp[i][j]\),故问题得到了解决。

代码如下:

for (i = 0; i < len_n; i++)
{
    temp = 0;
    for (j = 0; j < len_m; j++)
    {
        now_val = dp[j];//now_val代表dp[i-1][j]的值
        if (strn[i] == strm[j])
            dp[j] = temp + 1;//代表dp[i-1][j-1]+1
        else
            dp[j] = max(dp[j - 1], dp[j]);//dp[j-1]代表dp[i][j-1]
        temp = now_val;//保留dp[i-1][j]的值
    }
}

空间复杂度:\(O(n)\)

时间复杂度优化

适用条件:序列中重复元素较少,最好为排列

思路:考虑每一个出现在\(strn\)的字符,在\(strm\)中找到其出现的所有位置并加以分类降序储存在数组中。再把每一个字符对应的坐标按照对应字符在\(strn\)中出现的下标**顺序排列成一个新序列\(M\),则\(M\)的LIS(最长上升子序列)即是所求答案。

例:

strn=abscsa
strm=adbsccab

则
a在strm的坐标为0、6
b在strm的坐标为2、7
s在strm的坐标为3
c在strm的坐标为4、5

则序列M为

6 0 7 2 3 5 4 3 6 0

LIS长度为5
故LCS长度为5

\(tips:\)

  1. 正确性:求出\(M\)的最长上升子序列保证了这些字符在\(strm\)中升序出现,又因为这些字符是按照在\(strn\)中的坐标升序排列的,故为两者的\(LCS\)。
  2. 选择降序排列坐标数组:防止同一个位置的字符被多次选取计算。
  3. 如何在\(O(n)\)时间内得到坐标数组:使用链表或者动态数组
void solve(char *str1, char *str2)
{
    len_n = strlen(str1), len_m = strlen(str2);
    for(int i = 0; i < len_n; i++)
    {
        inv[str1[i] - ' '] = true;
        head[str1[i] - ' '] = -1;
    }
    for(int i = 0; i < len_m; i++)
    {
        if(inv[str2[i] - ' ']) 
        {   
            next[i] = head[str2[i] - ' '];
            head[str2[i] - ' '] = i;   
        }
    }
    for(int i = 0; i < len_n; i++)
    {
        int now_pos = head[str1[i] - ' '];
        while (now_pos != -1)
        {
            str[str_len++] = now_pos;//同时实现了降序排序的要求
            now_pos = next[now_pos];
        }
    }
}

上述代码实现了构造序列\(M\)(即是代码中的\(str\))的任务。

时间复杂度:对于没有重复元素的序列,时间复杂度为\(O(n)\),随序列中元素重复度升高而升高,最坏可以为\(O(n^2)\),即整个序列只有一种元素。

求解\(LIS\)可以使用树状数组优化,时间复杂度为\(O(nlogn)\)

因此总复杂度较好情况下为\(O(nlogn)\)。

这篇关于LCS算法及其时空优化的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!