求最长子序列的长度

求最长子序列的长度求最长子序列的长度一，最长递增子序列问题的描述设L=是n个不同的实数的序列，L的递增子序列是这样一个子序列12n Lin=，其中k是对序列L=按递增排好序的序列。那么显12n12n 然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。最长公共子序列问题用动态规划的算法可解。设Li=,Xj=，它们分别为L和X的子序列。令C[i,j]为Li与Xj的最长公共子12j 序列的长度。则有如下的递推方程: 2这可以用时间复杂度为O(n)的算法求解，由...

求最长子序列的长度一，最长递增子序列问题的描述设L=是n个不同的实数的序列，L的递增子序列是这样一个子序列12n Lin=，其中k是对序列L=按递增排好序的序列。那么显12n12n 然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。最长公共子序列问题用动态规划的算法可解。设Li=< a,a,…,a>,Xj=< 12ib,b,…,b>，它们分别为L和X的子序列。令C[i,j]为Li与Xj的最长公共子12j 序列的长度。则有如下的递推方程: 2这可以用时间复杂度为O(n)的算法求解，由于这个算法上课时讲过，所以具体代码在此略去。求最长递增子序列的算法时间复杂度由排序所用的O(nlogn) 22的时间加上求LCS的O(n)的时间，算法的最坏时间复杂度为O(nlogn)，O(n) 2,O(n)。三，第二种算法:动态规划法设f(i)表示L中以a为末元素的最长递增子序列的长度。则有如下的递推方i 程: 这个递推方程的意思是，在求以a为末元素的最长递增子序列时，找到所有序i 号在L前面且小于a的元素a，即jf[i]-1) f[i]=f[j]+1;//更新f[i]的值。 } } System.out.println(f[n-1]); } 这个算法有两层循环，外层循环次数为n-1次，内层循环次数为i次，算法的时间复杂度 2所以T(n)=O(n)。这个算法的最坏时间复杂度与第一种算法的阶是相同的。但这个算法没有排序的时间，所以时间复杂度要优于第一种算法。

                    本文档为【求最长子序列的长度】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

你可能还喜欢

最新资料

资料动态

专题动态

is_589748

暂无简介~

格式：doc

大小：13KB

软件：Word

页数：0

分类：生活休闲

上传时间：2017-10-21

浏览量：10

热点搜索

九年级语文上册第3单元综合测试题（新版）新人教版来料检验流程图浙江省餐饮服务食品切配工用具色标管理操作指南（试行）浙食药监食2013 35号 2019年四川省成都七中高考数学一诊试卷（文科）+ 加油站特种作业人员安全培训 [复习]2013年小学5年级日记精选 (46) .兰州西固华都天韵童学馆举办开蒙仪式 [业务]秋夜将晓出篱门迎凉有感阅读设计全国统一安装工程预算定额江苏省单价估价表 2015届第一次模拟15套题(生活与哲学选择题) 六年级下册简易方程练习题「2#宿舍楼地基子分部、分部工程质量验收记录」酒店PA工作职责及流程(doc 15) 百家讲坛2004年4月14日《水浒传》的思想倾向石昌渝_shtml 九年级语文上册第3单元综合测试题（新版）新人教版来料检验流程图浙江省餐饮服务食品切配工用具色标管理操作指南（试行）浙食药监食2013 35号 2019年四川省成都七中高考数学一诊试卷（文科）+ 加油站特种作业人员安全培训 [复习]2013年小学5年级日记精选 (46) .兰州西固华都天韵童学馆举办开蒙仪式 [业务]秋夜将晓出篱门迎凉有感阅读设计全国统一安装工程预算定额江苏省单价估价表 2015届第一次模拟15套题(生活与哲学选择题) 六年级下册简易方程练习题「2#宿舍楼地基子分部、分部工程质量验收记录」酒店PA工作职责及流程(doc 15) 百家讲坛2004年4月14日《水浒传》的思想倾向石昌渝_shtml