设计网站的结构时,国家的企业信息网,html5 wap 网站模板,大连装修公司哪家好最长递增子序列问题是一个很基本、较常见的小问题#xff0c;但这个问题的求解方法却并不那么显而易见#xff0c;需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想#xff0c;能够锻炼设计较复杂算法的思维…
最长递增子序列问题是一个很基本、较常见的小问题但这个问题的求解方法却并不那么显而易见需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想能够锻炼设计较复杂算法的思维我对这个问题进行了较深入的分析思考得出了几种复杂度不同算法并给出了分析和证明。
一 最长递增子序列问题的描述
设La1,a2,…,an是n个不同的实数的序列L的递增子序列是这样一个子序列LinaK1,ak2,…,akm其中k1k2…km且aK1ak2…akm。求最大的m值。
二 第一种算法转化为LCS问题求解
设序列Xb1,b2,…,bn是对序列La1,a2,…,an按递增排好序的序列。那么显然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。 最长公共子序列问题用动态规划的算法可解。设Li a1,a2,…,ai,Xj b1,b2,…,bj它们分别为L和X的子序列。令C[i,j]为Li与Xj的最长公共子序列的长度。则有如下的递推方程
这可以用时间复杂度为O(n2)的算法求解由于这个算法上课时讲过所以具体代码在此略去。求最长递增子序列的算法时间复杂度由排序所用的O(nlogn)的时间加上求LCS的O(n2)的时间算法的最坏时间复杂度为O(nlogn)O(n2)O(n2)。
三 第二种算法动态规划法 设f(i)表示L中以ai为末元素的最长递增子序列的长度。则有如下的递推方程
这个递推方程的意思是在求以ai为末元素的最长递增子序列时找到所有序号在L前面且小于ai的元素aj即ji且ajai。如果这样的元素存在那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j)把其中最大的f(j)选出来那么f(i)就等于最大的f(j)加上1即以ai为末元素的最长递增子序列等于以使f(j)最大的那个aj为末元素的递增子序列最末再加上ai如果这样的元素不存在那么ai自身构成一个长度为1的以ai为末元素的递增子序列。
这个算法由Java实现的代码如下
public void lis(float[] L) { int n L.length; int[] f new int[n];//用于存放f(i)值 f[0]1;//以第a1为末元素的最长递增子序列长度为1 for(int i 1;in;i)//循环n-1次 { f[i]1;//f[i]的最小值为1 for(int j0;ji;j)//循环i 次 { if(L[j]L[i]f[j]f[i]-1) f[i]f[j]1;//更新f[i]的值。 } } System.out.println(f[n-1]); } 这个算法有两层循环外层循环次数为n-1次内层循环次数为i次算法的时间复杂度
所以T(n)O(n2)。这个算法的最坏时间复杂度与第一种算法的阶是相同的。但这个算法没有排序的时间所以时间复杂度要优于第一种算法。
四 对第二种算法的改进
在第二种算法中在计算每一个f(i)时都要找出最大的f(j)(ji)来由于f(j)没有顺序只能顺序查找满足ajai最大的f(j)如果能将让f(j)有序就可以使用二分查找这样算法的时间复杂度就可能降到O(nlogn)。于是想到用一个数组B来存储“子序列的”最大递增子序列的最末元素即有
B[f(j)] aj
在计算f(i)时在数组B中用二分查找法找到满足ji且B[f(j)]ajai的最大的j,并将B[f[j]1]置为ai。下面先写出代码再证明算法的证明性。用Java实现的代码如下
lis1(float[] L)
{ int n L.length; float[] B new float[n1];//数组B B[0]-10000;//把B[0]设为最小假设任何输入都大于-10000 B[1]L[0];//初始时最大递增子序列长度为1的最末元素为a1 int Len 1;//Len为当前最大递增子序列长度初始化为1 int p,r,m;//p,r,m分别为二分查找的上界下界和中点 for(int i 1;in;i) { p0;rLen; while(pr)//二分查找最末元素小于ai1的长度最大的最大递增子序列 { m (pr)/2; if(B[m]L[i]) p m1; else r m-1; } B[p] L[i];//将长度为p的最大递增子序列的当前最末元素置为ai1; if(pLen) Len;//更新当前最大递增子序列长度 } System.out.println(Len);
} 现在来证明这个算法为什么是正确的。要使算法正确只须证如下命题
命题1每一次循环结束数组B中元素总是按递增顺序排列的。
证明用数学归纳法对循环次数进行归纳。
当i0时即程序还没进入循环时命题显然成立。
设ik时命题成立当ik时假设存在j1j2,B[j1]B[j2]因为第i次循环之前数组B是递增的因此第i次循环时B[j1]或B[j2]必有一个更新假设B[j1]被更新为元素ai1由于ai1B[j1] B[j2]按算法ai1应更新B[j2]才对因此产生矛盾假设B[j2]被更新设更新前的元素为s,更新后的元素为ai1则由算法可知第i次循环前有B[j2]s ai1 B[j1]这与归纳假设矛盾。命题得证。
命题2B[c]中存储的元素是当前所有最长递增子序列长度为c的序列中最小的最末元素即设当前循环次数为i有B[c]{aj| f(k)f(j)c∧k,j≤i1→aj≤ak}(f(i)为与第二种算法中的f(i)含义相同)。
证明程序中每次用元素ai更新B[c]时(cf(i))设B[c]原来的值为s则必有ais不然ai就能接在s的后面形成长度为c1的最长递增子序列而更新B[c1]而不是B[c]了。所有B[c]中存放的总是当前长度为的最长递增子序列中最小的最末元素。
命题3设第i次循环后得到的p为p(i1)那么p(i)为以元素ai为最末元素的最长递增子序列的长度。
证明只须证p(i)等于第二种算法中的f(i)。显然一定有p(i)f(i)。假设p(i)f(i)那么有两种情况第一种情况是由二分查找法找到的p(i)不是数组B中能让ai接在后面成为新的最长递增子序列的最大的元素由命题1和二分查找的方法可知这是不可能的第二种情况是能让ai接在后面形成长于p(i)的最长递增子序列的元素不在数组B中由命题2可知这是不可能的因为B[c]中存放的是最末元素最小的长度为c的最长递增子序列的最末元素若ai能接在长度为L(L p(i))的最长递增子序列后面就应该能接在B[L]后面那么就应该有p(i)L,与L p(i)矛盾。因此一定有p(i)f(i)命题得证。
算法的循环次数为n每次循环二分查找用时logn所以算法的时间复杂度为O(nlogn)。这个算法在第二种算法的基础上得到了较好的改进。
五 总结
本论文只给出了计算解的大小而没有给出构造解的方法因为我认为计算解的大小的算法已能给出对问题的本质认识只要计算解大小的算法设计出构造解就只是技术细节的问题了而我关心的是怎样对问题得到很好的认识而设计出良好的算法。以上几种算法已用Java实现都能得到正确的结果。在设计和改进算法时用到了基本的算法设计和分析、证明的基本方法很好的锻炼了设计与分析算法的思维能力让我从感性上认识到算法分析与设计的重要性并且感受了算法分析、设计和改进的乐趣。
