最长递增子序列.docx
- 文档编号:10658348
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:13
- 大小:24.81KB
最长递增子序列.docx
《最长递增子序列.docx》由会员分享,可在线阅读,更多相关《最长递增子序列.docx(13页珍藏版)》请在冰点文库上搜索。
最长递增子序列
最长递增子序列
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么
显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。
由于这个问题能运用学过
的基本的算法分析和设计的方法与思想,能够锻炼设计较复杂算法的思维,我对这个问题进行了
较深入的分析思考,得出了几种复杂度不同算法,并给出了分析和证明。
设L=是n个不同的实数的序列,L的递增子序列是这样一个子序列12n
Lin=,其中k 求最大的m值。 K1k2km12mK1k2km LCS 设序列X=是对序列L=按递增排好序的序列。 那么显然X与L12n12n 的最长公共子序列即为L的最长递增子序列。 这样就把求最长递增子序列的问题转化为求最长 公共子序列问题LCS了。 最长公共子序列问题用动态规划的算法可解。 设Li=,Xj=,12i12j 它们分别为L和X的子序列。 令C[i,j]为Li与Xj的最长公共子序列的长度。 这可以用时间复 2杂度为O(n)的算法求解,由于这个算法上课时讲过,所以具体代码在此略去。 求最长递增子序 2列的算法时间复杂度由排序所用的O(nlogn)的时间加上求LCS的O(n)的时间,算法的最坏 22时间复杂度为O(nlogn)+O(n)=O(n)。 设f(i)表示L中以a末元素的最长递增子序列的长度。 则有如下的递推方程: i 这个递推方程的意思是,在求以a为末元素的最长递增子序列时,找到所有序号在L前面且小i 于a的元素a,即j 如果这样的元素存在,那么对所有a,都有一个以a为末元素ijjijj的最长递增子序列的长度f(j),把其中最大的f(j)选出来,那么f(i)就等于最大的f(j)加上1, 即以a为末元素的最长递增子序列,等于以使f(j)最大的那个a为末元素的递增子序列最末再ij加上a;如果这样的元素不存在,那么a自身构成一个长度为1的以a为末元素的递增子序列。 iii这个算法由Java实现的代码如下: publicvoidlis(float[]L) { intn=L.length; int[]f=newint[n];//用于存放f(i)值; f[0]=1;//以第a1为末元素的最长递增子序列长度为1; for(inti=1;i { f[i]=1;//f[i]的最小值为1; for(intj=0;j { if(L[j] f[i]=f[j]+1;//更新f[i]的值。 } } System.out.println(f[n-1]); } 这个算法有两层循环,外层循环次数为n-1次,内层循环次数为i次,算法的时间复杂度 2所以T(n)=O(n)。 这个算法的最坏时间复杂度与第一种算法的阶是相同的。 但这个算法没有排 序的时间,所以时间复杂度要优于第一种算法。 在第二种算法中,在计算每一个f(i)时,都要找出最大的f(j)(j
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最长 递增 序列