贪心算法-最优合并问题

上机04实验名称一、问题11、问题描述一、最优合并问题给定k个有序序列s1,s2,...,sk,用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少，编程实现该算法并证明算法的正确性。2、算法设计思想贪心算法3、算法过程描述原问题S={S1，S2，S3，S4..Sn}，（合并顺序）设最优解为Ck(最少合并次数)设Si,Sj为最短的两个序列反证法证明贪心选择性质：设有另一个最优解Ck1（没有使用贪心选择性质，即没有先合并Si,Sj）构造一课二叉合并树Sk为任意序列，Sksi,sj由图可知，Ck-Ck1=(Sk+Sj-1)+(Si+Sj+si-1)-(Si+sj-1)+(Si+Sj+Sk-1)=Sk-Si0因此Ck1不是最优解，因此具有贪心选择性质最优子结构证明：S={S1，S2，S3，S4….Sn}记Si和Sj的合并为（Si,Sj）-Si+jS=S-{S1,S2}∪Si+j∴Ck=Ck`+(Si+Sj-1)4、算法实现及运行结果#includestdio.h#includealgorithmusingnamespacestd;//计算最优值intminSum(int*a,intm){SSkSjSiSkSjSiintb[m];intsum=0;for(inti=0;im;i++){b[i]=a[i];}while(m1){sort(b,b+m);b[0]=b[1]+b[0];sum+=b[0]-1;for(inti=1;im-1;i++)b[i]=b[i+1];m--;}returnsum;}intmain(){intn;printf(请输入序列个数:\n);scanf(%d,&n);inta[n+1];printf(请输入各个序列长度:\n);for(inti=0;in;i++){scanf(%d,&a[i]);}printf(最少比较次数为：%d\n,minSum(a,n));return0;}5、算法复杂度分析及算法改进时间复杂度：排序：O(nlogn)，合并(n-1)(2*O(1)+O(n))=O(n^2)使用堆排序：（n-1）(2*O(logn)+O(logn))=O(nlogn)