算法导论习题解答：提高编程竞争力

需积分: 32 135 浏览量更新于2024-07-26 收藏 257KB PDF 举报

"《算法导论》第二版课后习题解答文档由Philip Bille提供，该文档主要针对Cormen、Leiserson和Rivest所著的《算法导论》中的部分练习题给出了初步的解决方案。作者强调，这个文档仅供个人参考，并非官方解答，可能存在错误，读者应自行尝试解决题目，仅在遇到困难或验证答案时作为最后求助。其中一道题目涉及插入排序与归并排序的时间复杂性比较。当输入规模n满足8n^2 < 64nlg(n)，即n < 8lg(n)，简化后得到2n/8 < n，这成立的条件为2 <= n <= 43。因此，对于n小于等于43的情况，作者建议修改归并排序算法，在输入大小不超过43时，使用插入排序来优化运行时间，以提升效率。另一部分提到的假设是所有月份有30天，而所有年份有365天，这是为了解决某些与日期计算相关的算法问题，可能是作为实际应用中的基础设定。文档处于不断更新中，最后一次更新日期为2002年12月9日，提醒读者在使用过程中可能需要关注最新的修正。这份资料是为学习者提供了一种学习算法和解决问题的辅助工具，鼓励独立思考，但不能替代深入理解和实际练习。"

Initialization: Before the ﬁrst 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 ﬁrst 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

n).

c. The HEAP-EXTRACT-MAX algorithm given in the text works ﬁne 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

n) and dominates the overall time spent by HEAP-EXTRACT-MAX.

剩余50页未读，继续阅读

驴头人酋长

粉丝: 18
资源: 7

算法导论习题解答：提高编程竞争力

算法导论课后答案中英文

算法导论第三版答案 pdf

机器人学导论jcraig课后答案

算法导论第三版答案中文pdf

算法导论 csdn pdf

awz3 算法导论 电子书

算法导论 baase gelder

mit算法导论 课件

算法导论 下载 csdn

算法导论第三版第四章答案

最新资源

awz3 算法导论电子书

mit算法导论课件

算法导论下载 csdn