Mark Allen Weiss 数据结构与算法分析 课后习题答案11.pdfVIP

Chapter 11: Amortized Analysis 11.1 When the number of trees after the insertions is more than the number before. 11.2 Although each insertion takes roughly log NO , and each DeleteMinO takes 2log NO actual time, our accounting system is charging these particular operations as 2 for the insertion and 3log NO−2 for the DeleteMin.O The total time is still the same; this is an accounting gimmick. If the number of insertions and DeleteMinsO are roughly equivalent, then it really is just a gimmick and not very meaningful; the bound has more significance if, for instance, there are NO insertions and OO (NO/ log NO) DeleteMinsO (in which case, the total time is linear). 11.3 Insert the sequence NO , NO + 1, NO − 1, NO + 2, NO − 2, NO + 3, ..., 1, 2NO into an initially empty skew heap. The right path has NO nodes, so any operation could take Ω(NO) time. 11.5 We implement DecreaseKey(X, H) as follows: If lowering the value of XO creates a heap order violation, then cut XO from its parent, which creates a new skew heap HO 1 with the new value of XO as a root, and also makes the old skew heap HO smaller. This operation might also increase the potential of HO , but only by at most log NO . We now merge HO and HO 1. The total amortized time of the MergeO is OO (log NO), so the total time of the DecreaseKeyO operation is OO (log NO). 11.8 For the zigO−zigO case, the actual cost is 2, and the potential change is R ( XO ) + R ( PO ) + R ( GO ) − R ( XO ) − R ( PO