Consider a stack that stores items that are collections of m elements. So one
could only push and pop a collection at a time. For this bulk stack, we will
call the operations Bush and Bop. Using the bulk stack as an underlying
structure, we want to implement a regular stack that can P ush and P op
individual elements.
Given a collection C that is on the top of the stack, to P ush an element we
can Bop C, add the element to it, and Bush it back on the stack. Similarly,
to P op an element, we can Bop C, delete it’s top element, and Bush it back
on the stack. We assume:
• we can check if the bulk stack is empty
• a collection C itself acts like a stack, so we can add and remove to/from
its “top” (P ush and P op) in O(1) time
• we can determine the number of elements in a collection C (which is
at least 0 and at most m)
• Bush and Bop take O(m) time
(a) One can keep a copy of the top collection “active” while performing
P ush and P op operations and refraining from using Bush and Bop until
P ush sees a full collection or P op sees an empty collection. Describe a sequence
of P ush and P op operations that still has an average of O(m) time
per operation.
(b) Describe a mechanism to achieve O(1) amortized time per P ush/P op
operation. Hint: keep two active collections. Do the analysis using the aggregate
method, the accounting method, and the potential method.
自学算法导论当中，看到第17章，网上看到这道题，感觉跟摊还分析没有关系啊。
请问大神们，这道题是属于哪种知识点？
