首页 / 算法 / 算法第二章上机实践报告
算法第二章上机实践报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法第二章上机实践报告,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2245字,纯文字阅读大概需要4分钟。
内容图文
1.实践题目名称:找第k小的数。
2.问题描述:设计一个平均时间为O(n)的算法,在n(1<=n<=1000)个无序的整数中找出第k小的数。
3.算法描述:由函数int partition(int a[],int left,int right)、int find(int a[],int left,int right,int k) 和 int main() 构成。
(1)函数int partition(int a[],int left,int right)的功能是根据a[left]~a[right]中的某个元素x( 如a[left] ) 对a[left]~a[right]进行划分,划分后的x所在位置的左段全小于等于x,右段全大于等于x,同时利用x所在的位置还可以计算出x是这批数据按升非降序排列的第几个数。
int partition(int a[],int left,int right){
将最左边的数值赋给x;
while(left<right){
while下标为right的数值大于或等于x且left小于right
right左移;
交换下标为left和right的数值;
while下标为left的数值小于于或等于x且left小于right
left右移;
交换下标为left和right的数值;
}
重新赋值x;
返回left;
(2)函数int find(int a[],int left,int right,int k),通过调用partition函数获得划分点,判断划分点是否第k小,若不是,递归调用find函数继续在左段或右段查找。
int find(int a[],int left,int right,int k){
调用partition函数,将其值赋值给变量p;
如果k-1等于p,输出数组a中下标为k-1的数值;
如果k-1小于p,递归调用find在(left,p-1)区间继续找;
如果k-1大于p,递归调用find在(p+1,right)区间继续找;
return 0;
}
(3)main函数。
int main(){
定义变量n,k;
输入n,k的值;
定义一个大小为1000的数组;
用for循环依次输入数组a;
调用find函数在(n-1,k)区间找数组a中第k大的数;
return 0;
}
4.算法时间及空间复杂度分析(要有分析过程):
时间复杂度:拿到这道题,我第一时间想到的方法就是直接排序然后输出第k小的数。但是题目要求设计一个平均时间为O(n)的算法,而第一个方法的时间复杂度不符合题目要求,所以并不可行。因此还是要运用学过的分治法和快速排序法。先用数组中的元素x对数组进行划分,分成左右两个区域,然后判断x是否为题目要求的第k小的数,若是,则输出,若不是则继续划分查找,以此类推,直到找到为止。这样就能达到题目要求的平均时间O(n)了。
空间复杂度:find函数中运用了递归,所以空间复杂度应为O(log n)。
5.心得体会(对本次实践收获及疑惑进行总结)
本次上机实践学会了用函数partition()对数组进行划分,相比于以往较为简单粗暴的直接排序然后输出的算法,更加的巧妙和高级。这一次在题目的要求之下学会了如何区运用更加精巧和高效率的算法去同一个解决问题。上机实践过程中前期对find函数的设计和快速排序算法不太理解,编程进度有点被卡住。在实践结束后,对函数的递归调用,分治法的思想以及数组区域的划分有了更深的了解和认识。
内容总结
以上是互联网集市为您收集整理的算法第二章上机实践报告全部内容,希望文章能够帮你解决算法第二章上机实践报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。