算法导论习题解析全集：从插入排序到归并排序

5星 · 超过95%的资源需积分: 27 118 浏览量更新于2024-08-02 收藏 257KB PDF 举报

"算法导论习题集-全的" 这篇文档是《算法导论》第二版的习题解答，由Philip Bille编撰。作者明确表示对内容的正确性不承担责任，这仅是一个对书中部分练习题的粗略解答建议。他鼓励读者首先自己尝试解决问题，仅将此文档作为最后的参考或验证答案之用。文档目前处于建设阶段，更新并不频繁。习题解答部分： 1.2-2 插入排序优于归并排序的情况是当8n^2 < 64n log n，解这个不等式可得n < 8log n，进一步简化为2^(n/8) < n。通过计算得出，这个条件在2 <= n <= 43时成立。这意味着对于大小为43或更小的输入，改用插入排序可以优化运行时间。为了改善归并排序的时间效率，可以设计一个混合算法，对于小于43个元素的数组，使用插入排序代替归并排序。 1-1 题目假设所有月份都有30天，所有年份都是365天。这部分可能涉及到日期和时间的处理，例如计算特定日期间的天数或进行日期操作。 1（未提供完整内容）：这部分可能是一个关于时间单位转换的问题，如秒、分钟之间的转换。完整的题目可能要求将某一时间量从秒转换成分钟或其他时间单位。这些习题反映了《算法导论》中的基本概念，包括排序算法（插入排序与归并排序的比较）、数学在算法分析中的应用以及可能的时间和日期处理。《算法导论》是一本经典的教材，涵盖了广泛的算法知识，包括但不限于排序、搜索、图算法、动态规划等。通过解决书中的习题，读者可以深入理解算法的工作原理，并提升分析和解决问题的能力。对于编程和计算机科学领域的学习者来说，这本书是不可或缺的参考资料。

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页未读，继续阅读

mountainclamber

粉丝: 0
资源: 1

算法导论习题解析全集：从插入排序到归并排序

算法导论习题解-相信大家都知道

算法导论第三版课后习题答案

算法导论习题算法导论习题解答

麻省算法导论全集-教程+讲义+答案

完整的算法导论习题答案 完整的算法导论习题答案

麻省理工学院-算法导论-课件习题 全

算法导论 习题

第二版的算法导论习题答案（1－35章）

算法导论习题答案

算法导论习题详解与解答全集

最新资源

完整的算法导论习题答案完整的算法导论习题答案

麻省理工学院-算法导论-课件习题全

算法导论习题