LCS算法及其时空优化
2022/2/24 12:51:37
本文主要是介绍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:\)
- 正确性:求出\(M\)的最长上升子序列保证了这些字符在\(strm\)中升序出现,又因为这些字符是按照在\(strn\)中的坐标升序排列的,故为两者的\(LCS\)。
- 选择降序排列坐标数组:防止同一个位置的字符被多次选取计算。
- 如何在\(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算法及其时空优化的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-06有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享