《算法设计与分析》实验报告：实验一（分治策略）
75 浏览量
2020-11-17
12:19:58
上传
评论 1
收藏 248KB PDF 举报
实验一
我保证没有抄袭别人作业!
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 规模的子问题
资源评论
