《Mark Allen Weiss 数据结构与算法分析 课后习题答案11》由会员分享，可在线阅读，更多相关《Mark Allen Weiss 数据结构与算法分析 课后习题答案11（3页珍藏版）》请在金锄头文库上搜索。
1、Chapter11:AmortizedAnalysis11.1When the number of trees after the insertions is more than the number before.11.2Although each insertion takes roughly log N?, and each DeleteMin? takes 2log N? actual time, our accounting system is charging these particular operations as 2 for the insertion and 3log N
2、?2 for the DeleteMin.? The total time is still the same; this is an accounting gimmick. If the number of insertions and DeleteMins? are roughly equivalent, then itreally is just a gimmick and not very meaningful; the bound has more significance if, for instance, there are N? insertions and O?(N?/ lo
3、g N?) DeleteMins? (in which case, the total time is linear).11.3Insert the sequence N?, N? + 1, N? 1, N? + 2, N? 2, N? + 3, ., 1, 2N? into an initially empty skew heap. The right path has N? nodes, so any operation could take (N?) time.11.5We implement DecreaseKey(X, H) as follows: If lowering the v
4、alue of X? creates a heap order violation, then cut X? from its parent, which creates a new skew heap H?1with the new value of X? as a root, and also makes the old skew heap H? smaller. This operation might also increase the potential of H?, but only by at most log N?. We now merge H? and H?1. The t
5、otal amortized time of the Merge? is O?(log N?), so the total time of the DecreaseKey? operation is O?(log N?).11.8Forthezig?zig?case,theactualcostis2,andthepotentialchangeis R?f?( X? ) + R?f?( P? ) + R?f?( G? ) Ri?( X? ) Ri?( P? ) Ri?( G? ).This gives an amortized time bound ofATzig?zig? = 2 + R?f?
6、( X? ) + R?f?( P? ) + R?f?( G? ) Ri?( X? ) Ri?( P? ) Ri?( G? )Since R?f?( X? ) = Ri?( G? ), this reduces to= 2 + R?f?( P? ) + R?f?( G? ) Ri?( X? ) Ri?( P? )Also, R?f?( X? ) R?f?( P? ) and Ri?( X? ) Ri?( P? ), soATzig?zig? 2 + R?f?( X? ) + R?f?( G? ) 2Ri?( X? )Since Si?( X? ) + S?f?( G? ) S?f?( X? ),
7、 it follows that Ri?( X? ) + R?f?( G? ) 2R?f?( X? ) 2. ThusATzig?zig? 3R?f?( X? ) 3Ri?( X? )11.9(a) Choose W?(i?) = 1/ N? for each item. Then for any access of node X?, R?f?( X? ) = 0, and Ri?( X? ) log N?, so the amortized access for each item is at most 3 log N? + 1, and the net potential drop ove
8、r the sequence is at most N? log N?, giving a bound of O?(M?log N? + M? + N?log N?), as claimed.(b) Assign a weight of qi?/M? to items i?. Then R?f?( X? ) = 0, Ri?( X? ) log(qi?/M?), so the amortized cost of accessing item i? is at most 3 log(M?/qi?) + 1, and the theorem follows immediately.11.10(a)
9、 To merge two splay trees T?1and T?2, we access each node in the smaller tree and insert it into the larger tree. Each time a node is accessed, it joins a tree that is at least-63-twice as large; thus a node can be inserted log N? times. This tells us that in any sequence of N?1 merges, there are at
10、 most N?log N? inserts, giving a time bound of O?(N?log2N?). This presumes that we keep track of the tree sizes. Philosophically, this is ugly since it defeats the purpose of self-adjustment.(b) Port and Moffet 6 suggest the following algorithm: If T?2is the smaller tree, insert its root into T?1. T
11、hen recursively merge the left subtrees of T?1and T?2, and recursively merge their right subtrees. This algorithm is not analyzed; a variant in which the median of T?2is splayed to the root first is with a claim of O?(N?log N?) for the sequence of merges.11.11The potential function is c? times the n
12、umber of insertions since the last rehashing step, where c? is a constant. For an insertion that doesnt require rehashing, the actual time is 1, and the potential increases by c?, for a cost of 1 + c?.If an insertion causes a table to be rehashed from size S? to 2S?, then the actual cost is 1 + dS?,
13、 where dS? represents the cost of initializing the new table and copying the old table back. A table that is rehashed when it reaches size S? was last rehashed at size S?/ 2, so S?/ 2 insertions had taken place prior to the rehash, and the initial potential was cS?/ 2. The new potential is 0, so the
14、 potential change is cS?/ 2, giving an amortized bound of (d? c?/ 2)S? + 1. We choose c? = 2d?, and obtain an O?(1) amortized bound in both cases.11.12We show that the amortized number of node splits is 1 per insertion. The potential func- tion is the number of three-child nodes in T?. If the actual
15、 number of nodes splits for an insertion is s?, then the change in the potential function is at most 1 s?, because each split converts a three-child node to two two-child nodes, but the parent of the last node split gains a third child (unless it is the root). Thus an insertion costs 1 node split, a
16、mor- tized. An N? node tree has N? units of potential that might be converted to actual time, so the total cost is O?(M? + N?). (If we start from an initially empty tree, then the bound is O?(M?).)11.13(a) This problem is similar to Exercise 3.22. The first four operations are easy to imple- ment by placing two stacks, SL?and SR?, next to each other (with bottoms touching). Wecan implement the fifth operation by usin
