首页 / 算法 / 算法第二章上机实践报告
算法第二章上机实践报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法第二章上机实践报告,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2714字,纯文字阅读大概需要4分钟。
内容图文
![算法第二章上机实践报告](/upload/InfoBanner/zyjiaocheng/850/596784da9d8a4a84ae1ce7d26e049614.jpg)
1.实践题目:两个有序序列的中位数
2.问题描述:
输入一个n(0<n<=100000),代表两个等长有序序列的长度,随后两行分别输入两个非降序序列,求出两个序列的合并后的中位数,中位数为合并后的有序序列中的第(n+1)/2个数,下标从0开始。
3.算法描述:
本题可采用多种方法求解,最初我们选用的算法时间复杂度为O(n),之后在老师的要求下,运用第二章所学知识(即分治法)进行改进,改进后时间复杂度为O(logN)。
若采用分治法的思想,则是在不断缩小问题的规模,最终合并子问题求解。
具体过程如下:
每次分别求取每个序列的中位数,并比较中位数的大小,中位数较大的序列截取比该中位数小的一则的序列作为新的序列,中位数较小的序列截取比该中位数大的一侧的序列作为新的序列(两段序列需等长),比较新得到的两个序列的中位数,不断递归截取直到序列的规模足够小(本题取两个序列的长度分别为2时停止递归,特殊情况序列长度为1,单独进行讨论),对剩余的序列进行简单的排序操作后可得到最终答案,需要注意的是递归过程中应保持序列长度一致。
递归算法代码如下:
int findMid(int a[],int b[],int la,int ra,int lb,int rb){ int mida=(la+ra)/2; int midb=(lb+rb)/2; if(ra-la==0) { if(a[la]<b[lb]) return a[la]; else return b[lb]; }//当两个序列的初始长度都只为1时,特殊情况特殊处理 if(ra-la==1) { int s[4]; s[0]=a[la]; s[1]=a[ra]; s[2]=b[lb]; s[3]=b[rb]; sort(s,s+4); return s[1]; }//进行简单排序(本题选用algorithm头文件自带函数sort),直接得出中位数 if(a[mida]<b[midb] ){ if(ra-mida>midb-lb)//调整子序列长度 return findMid(a,b,mida,ra,lb,midb+1);//调整子序列长度,使得两段序列等长 else return findMid(a,b,mida,ra,lb,midb); } if(a[mida]>b[midb] ){ if(mida-la<rb-midb)//调整子序列长度 return findMid(a,b,la,mida+1,midb,rb);//调整子序列长度,使得两段序列等长 else return findMid(a,b,la,mida,midb,rb); } }
4.算法分析:
时间复杂度:该算法在每步将问题分成规模为N/2的1个子问题,由求规模为N的两个有序序列的中位数转变为求规模为N/2的两个有序序列的中位数。在划分操作时,直接取下标进行划分,复杂度为O(1);在合并子问题时,只需对4个数进行简单的排序,时间复杂度可看做O(1),主定理求解后,最终得出算法的时间复杂度为O(logn)。
空间复杂度:因存储数组需要存储空间,规模为O(n),而排序时为了方便使用一个辅助数组,规模为O(1),最终得出空间复杂度为O (n)。
5.心得体会:
此次合作是我和搭档的第二次合作,比较遗憾的是他在实验上机前就已经完成提交了代码,但我们还是一起交流了彼此的意见,对代码进行了改进。此题是改进幅度最大的一道,算是重新编写了代码(因为最初用的算法时间复杂度为O(N),在老师的要求下改进为O(logN)),但遗憾的是未能在上机时间内将其完善。我们改进的思路是对的,但由于一些小疏忽(最致命的小错误就是调用递归算法时忘记在前面加上return,导致我们进度滞塞,挠头踌躇,可能是因为我们两人太过急切于完成题目),还有一个错误是编完代码后发现只能处理大部分问题,后来发现是没有注意调整子序列的长度,导致截取序列的时候出现错误,两段序列不等长。按照我搭档的话来说就是感觉还是对分治法的使用不够熟练,没能够调整好子问题规模的大小。
内容总结
以上是互联网集市为您收集整理的算法第二章上机实践报告全部内容,希望文章能够帮你解决算法第二章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。