没有合适的资源?快使用搜索试试~ 我知道了~
首页算法导论课后习题解:从插入排序到归并排序优化
算法导论课后习题解:从插入排序到归并排序优化
需积分: 32 0 下载量 175 浏览量
更新于2024-08-02
收藏 257KB PDF 举报
"算法导论课后习题答案" 这篇文档提供了《算法导论》第二版的课后习题解决方案,由Philip Bille编撰。他明确指出,文档中的解答可能存在错误,鼓励读者在遇到问题时自行尝试解决,并欢迎对错误或更好的解法提出反馈。文档的目的是作为最后的参考资料或用来检验自己的解题思路是否正确。 在阅读《算法导论》的过程中,解决课后习题是深入理解算法的关键。文档中提到了一个具体的习题对比——在特定情况下插入排序优于归并排序。当8n^2小于64n log n时,插入排序的效率更高,解这个不等式得到n小于8 log n,进一步简化得到2n/8小于n。这在n等于2到43之间成立,这是通过计算得出的。 另一个习题涉及优化归并排序的时间复杂度。建议在输入规模为43或更小时改用插入排序,以提高运行效率。这是因为对于小规模数据,插入排序的常数因子影响较小,可能会比归并排序更快。 此外,文档还提醒读者注意,该文档尚处于建设中,更新并不频繁。作者鼓励读者享受算法学习的过程,并祝他们在算法探索中取得乐趣。 这些习题解答涵盖了算法分析的基本概念,如时间复杂度比较、算法优化以及实际问题的计算推理,这些都是理解和应用算法的基础。通过解决这些习题,读者可以深化对排序算法如插入排序和归并排序的理解,以及如何根据问题规模选择合适的算法。同时,它也强调了独立思考和解决问题能力的重要性,这在计算机科学的学习和实践中至关重要。
资源详情
资源推荐
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
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
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页未读,继续阅读
i_am_a_leaner
- 粉丝: 0
- 资源: 11
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 最优条件下三次B样条小波边缘检测算子研究
- 深入解析:wav文件格式结构
- JIRA系统配置指南:代理与SSL设置
- 入门必备:电阻电容识别全解析
- U盘制作启动盘:详细教程解决无光驱装系统难题
- Eclipse快捷键大全:提升开发效率的必备秘籍
- C++ Primer Plus中文版:深入学习C++编程必备
- Eclipse常用快捷键汇总与操作指南
- JavaScript作用域解析与面向对象基础
- 软通动力Java笔试题解析
- 自定义标签配置与使用指南
- Android Intent深度解析:组件通信与广播机制
- 增强MyEclipse代码提示功能设置教程
- x86下VMware环境中Openwrt编译与LuCI集成指南
- S3C2440A嵌入式终端电源管理系统设计探讨
- Intel DTCP-IP技术在数字家庭中的内容保护
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功