算法设计与分析第三章1
需积分: 0 162 浏览量
2022-08-03
18:14:42
上传
评论
收藏 350KB PDF 举报
算法设计与分析第三章学习指南
视频
https://www.icourse163.org/course/HIT-356006
算法设计与分析(基础篇) 第三讲
阅读
算法导论(第三版) 4.1 节，4.2 节，第 9 章，第 30 章，33.3 节，33.4 节，第 27 章
(选学)
练习题
3.1 给定平面上 n 个点，求其中的一点对，使得在 n 个点的所有点对中，该点对的距离最小。
严格地说，最接近点对可能多于 1 对。为了简单起见，这里只限于找其中的一对。
（1）设计一个时间复杂度为 O(n
2
)的算法求距离最近的点对，要求写出算法伪代码；
（2）利用分治的思想设计一个时间复杂度为 O(nlogn)的算法求距离最近的点对，要求写出
算法伪代码。
3.2 对于平面上的两个点 p1=(x1, y1)和 p2=(x2,y2)，如果 x1<=x2 且 y1<=y2，则 p2 支配 p1，
给定平面上的 n 个点，请设计算法求其中没有被任何其他点支配的点。
3.3 设计一个分治算法，在一个 2 维平面上求 n 个点中距离最近的两个点，要求时间复杂性
是 o(n
2
)，请写出算法伪代码并分析时间复杂性。
3.4 阅读 https://oi-wiki.org/math/quick-pow/学习基于分治思想的“快速幂”算法。设计一个通
过矩阵运算，在 O(logN)时间内计算斐波那契数列第 N 项的算法。
3.5 给定一个数组 A，任务是设计一个算法求得数组中的“主元素”，即在数组中个数超过数
组总元素个数一半的元素。但是数组中元素的数据类型可能是复杂类型，这意味着数组中的
元素进能够比较是否相等而不存在序关系，设对于两个元素 A[i]和 A[j]，判定是否 A[i]=A[j]
需要常数时间。
(1) 设计一个时间复杂性为 O(n log n)的算法解此问题
(2) 设计一个时间复杂性为 O(n)的算法解此问题.
3.6 对于给定的 n 个元素的数组 A[1..n],要求从中找出第 k 小的元素。请设计分治算法解决
这个问题，要求算法的平均时间复杂度是 O(n)。答案要求包含以下内容：（1）用简明的自
然语言表述算法的基本思想；（2）用伪代码描述算法；（3）分析算法的时间复杂度。
3.7 给定实数数组 A[1:n]，试设计一个分治算法找出其中的最小元素和最大元素，使得比较
操作的总次数严格小于 2(n-1)。答案要求包含以下内容：（1）用简明的自然语言表述算法的
基本思想；（2）用伪代码描述算法；（3）分析算法的时间复杂度。
3.8 有长度为 N 的数组 A、B，每个数组中存储的浮点数已经升序排列。设计一个 O(logn)
时间的分治算法，找出这 2n 个数的中位数。证明算法的正确性。
3.9 设计分治算法求解下述问题：
输入：一个一维整数数组 A(其中元素可能是正数也可能是负数)
输出：A 的连续子数组，要求其和最大
例如，输入数组是{-2, -5, 6, -2, -3, 1, 5, -6}，其结果是{6, -2, -3, 1, 5},其和为 7.
要求: (1) 算法时间复杂度为 O(nlogn)；(2) 写出算法伪代码；(3) 分析算法时间复杂度
3.10 设计一个“三路归并”的排序算法，并分析它的时间复杂性。
评论0