实验一
我保证没有抄袭别人作业!
1. 实验题目
必做：
n 用分治思想设计实现二分搜索、合并排序，并且用不同数据量进行实验对比分析。
选做：
阶乘（递归与分治）。
2. 实验目的
掌握设计算法的分治策略,通过实验学习分治策略 设计技巧, 理解递归的概念验证二分
搜索的时间复杂度。
掌握算法效率的分析和实验验证方法。
3. 算法设计
3.1 分治法基本思想
将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题相互独立且与原问
题相同。然后递归的解这些子问题，然后将这些子问题的解合并得到原问题的解。
3.2 二分搜索技术
分解（devide）：
将 n 个元素分成个数大致相同的两半。此时，原问题 a[n]->子问题 a[1,n/2]与 a[2/n,n]
解决（conquer）:
取 a[n/2]与欲查找的 x 作比较。
如果 x=a[n/2]，则找到 x，算法终止。
如果 x<a[n/2]，则我们只要在数组 a 的左半部继续搜索 x。
如果 x>a[n/2]，则我们只要在数组 a 的右 半部继续搜索 x。
合并（combine）：
此结果无需合并。
3.3 合并排序
分解（devide）：
将 n 个元素分成个数大致相同的两半。此时，原问题 a[n]->子问题 a[1,n/2]与 a[2/n,n]
解决（conquer）:
递归解 n/2 规模的子问题
weixin_44771252
- 粉丝: 3
- 资源: 2
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0