没有合适的资源?快使用搜索试试~ 我知道了~
首页MIT算法导论讲义与43以内插入排序优化
MIT算法导论讲义与43以内插入排序优化
需积分: 32 4 下载量 157 浏览量
更新于2024-07-24
收藏 257KB PDF 举报
《麻省理工学院算法导论讲义与答案》是一份由Philip Bille编写的文档,旨在为Cormen、Leiserson和Rivest所著的《算法导论》第二版中的部分练习提供一种模糊的解答参考。作者强调,这份讲义不承担任何责任,可能存在许多错误,并建议读者在独立尝试解决问题后再查阅,作为最后的辅助手段或确认理解是否正确。 该讲义特别关注了某些具体问题的解答,如第1.2-2节中,讨论了插入排序(Insertion Sort)相对于归并排序(Merge Sort)在特定情况下的优势。当输入规模n满足8n^2 < 64nlg(n),即n < 8lg(n),大约n < 43时,插入排序的运行时间优于归并排序。作者建议在处理输入大小为43或更小的情况时,修改归并排序算法,利用插入排序来提升效率。 另一个例子是第1-1题,它假设所有月份都有30天,而所有年份有365天,这可能是在讨论日历相关的算法问题,或者是在设置一个简化的时间管理模型。 值得注意的是,这份讲义处于持续更新之中,但并不频繁,因此读者可能需要保持一定的耐心和独立思考能力,因为某些内容可能尚未完全更新到最新版本。最后,作者鼓励读者在学习过程中享受算法的乐趣,不断挑战自我,提升算法技能。 《MIT算法导论讲义及答案》是一份实用的辅助资料,适用于那些希望深入理解算法原理和解决实际问题的学生和专业人士,同时提醒他们保持批判性思维,通过实践深化对算法的理解。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/7037865/bg9.jpg)
Initialization: Before the first iteration of the while the only change of the max-heap is that A[i]
is increased an may therefore violate the max-heap property.
Maintenance: Immediately before the iteration i and the child that violated the max-heap prop-
erty has been exchanged thus restoring the max-heap property between these. This can only
destroy the max-heap property between i and the parent of i.
Termination: The termination condition of the while states that at the end of the iteration the
max-heap property between i and its parent is restored or the i is the root of the heap.
We see by the loop invariant that the heap property is restored at end of the iteration.
6.5 − 7
Algorithm 5 HEAP-DELETE(A, i)
Input: A max-heap A and integers i.
Output: The heap A with the element a position i deleted.
A[i] ↔A[heap-size[A]]
heap-size[A] ←heap-size[A] − 1
key ←A[i]
if key 6 A[PARENT(i)] then
MAX-HEAPIFY(A, i)
else
while i > 1 and A[PARENT(i)] < key do
A[i] ↔A[PARENT(i)]
i ←PARENT(i)
end while
end if
6.5 − 8
Given k sorted lists with a total of n elements show how to merge them in O(n lg k) time. Insert
all k elements a position 1 from each list into a heap. Use EXTRACT-MAX to obtain the first element
of the merged list. Insert element at position 2 from the list where the largest element originally
came from into the heap. Continuing in this fashion yields the desired algorithm. Clearly the
running time is O(n lg k).
6 − 2
a. A d-ary heap can be implemented using a dimensional array as follows. The root is kept in
A[1], its d children are kept in order in A[2] through A[d+1] and so on. The procedures to map a
node with index i to its parent and its jth child are given by:
D-ARY-PARENT(i)
return b(i − 2)/d + 1c
D-ARY-CHILD(i, j)
return d(i − 1) + j + 1
b. Since each node has d children the height of the tree is Θ(log
d
n).
c. The HEAP-EXTRACT-MAX algorithm given in the text works fine for d-ary heaps; the problem
is MAX-HEAPIFY. Here we need to compare the argument node to all its children. This takes
Θ(d log
d
n) and dominates the overall time spent by HEAP-EXTRACT-MAX.
9
![](https://csdnimg.cn/release/download_crawler_static/7037865/bga.jpg)
d. The MAX-HEAP-INSERT given in the text works fine as well. The worst-case running time is
the height of the heap, that is Θ(log
d
n).
e. The HEAP-INCREASE-KEY algorithm given in the text works fine.
10
![](https://csdnimg.cn/release/download_crawler_static/7037865/bgb.jpg)
7.1 − 2
When all the elements in A are the same, notice that the comparison in line 4 of PARTITION is
always satified and i therefore is incremented in each iteration. Since initially i ←p − 1 and i + 1
is returned the returned value is r − 1.
To make PARTITION return (p + r)/2 when all elements are the same, simply modify the algo-
rithm to check for this case explicitly.
7.1 − 3
The running time of PARTITION is Θ(n) since each iteration of the for loop involves a constant
number of operations and there is Θ(n) iterations in total.
7.1 − 4
To make QUICKSORT sort in nonincreasing order replace the 6 comparison in PARTITION line 4
with >.
7.2 − 2
If the elements in A are the same, then by exercise 7.1 − 2 the returned element from each call
to PARTITION(A, p, r) is r − 1 thus yielding the worst-case partitioning. The total running time is
easily seen to be Θ(n
2
).
7.2 − 3
If the elements in A are distinct and sorted in decreasing order then, as in the previous exercise,
we have worst-case partitioning. The running time is again Θ(n
2
).
7 − 4
a. Clearly, the QUICKSORT’ does exactly the same as the original QUICKSORT and therefore works
correctly.
b. Worst-case partitioning can cause the stack depth of QUICKSORT’ to be Θ(n).
c. If we recursively call QUICKSORT’ on the smallest subarray returned by PARTITION we will
avoid the problem and retain a O(lg n) bound on the stack depth.
11
剩余50页未读,继续阅读
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
sunshine7415
- 粉丝: 0
- 资源: 3
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- AirKiss技术详解:无线传递信息与智能家居连接
- Hibernate主键生成策略详解
- 操作系统实验:位示图法管理磁盘空闲空间
- JSON详解:数据交换的主流格式
- Win7安装Ubuntu双系统详细指南
- FPGA内部结构与工作原理探索
- 信用评分模型解析:WOE、IV与ROC
- 使用LVS+Keepalived构建高可用负载均衡集群
- 微信小程序驱动餐饮与服装业创新转型:便捷管理与低成本优势
- 机器学习入门指南:从基础到进阶
- 解决Win7 IIS配置错误500.22与0x80070032
- SQL-DFS:优化HDFS小文件存储的解决方案
- Hadoop、Hbase、Spark环境部署与主机配置详解
- Kisso:加密会话Cookie实现的单点登录SSO
- OpenCV读取与拼接多幅图像教程
- QT实战:轻松生成与解析JSON数据
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)