算法第二章实验报告
2021/10/1 22:40:38
本文主要是介绍算法第二章实验报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
算法第二章实验报告
实践题目名称
7-3 两个有序序列的中位数
问题描述:
已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,A**N−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数(A0为第1个数)。
算法描述
本题采用了分治中的二分法。 主要体现在寻找第n个值时,先二分取2个数组的中位数。(另数组为a[n],b[n])
若a的中位数比b的大,由于数组为非降序排列,可知,第n个数在a[0]-a[mid]和b[mid]-b[n]之间。反之,则在b[0]-b[mid]和a[mid]-a[n]之间。如此循环取剩余数组的中位数直至left==right退出循环。此时a[right]和b[right]小的即为解。
do while(right1 != left1 || right2 != left2) { if(a[mid1] == b[mid2]) return a[mid1]; if(a[mid1] < b[mid2]) { left1 = mid1 + (right1 - left1+1)%2; right2 = mid2; } else { right1 = mid1; left2 = left2 + (right2 - left2+1)%2; } }
算法时间复杂度及空间复杂度分析
本题只需查找,无需排序且数组长度相等。
时间复杂度即为 O(logn)
空间复杂度 O(n)
心得体会
本题在对分比较时,相对难以找到其对分后,左右边界移动规律 以及 循环退出条件。 可以在纸上进行一定规模的数据演练,从而查找规律。
分治的个人体会和思考
分治是对去年学习的递归以及排序的加深应用,从而实现高效排序。
而分治在一些特殊方面,没有亮眼的表现,在使用前可进行算法时间复杂度的比较,并对递归关系公式进行优化以谋求缩减时间。
这篇关于算法第二章实验报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)