17.1 Aggregate analysis

17.1-1

If the set of stack operations included a \(\text{MULTIPUSH}\) operation, which pushses \(k\) items onto the stack, would the \(O(1)\) bound on the amortized cost of stack operations continue to hold?

No. The time complexity of such a series of operations depends on the number of pushes (pops vice versa) could be made. Since one \(\text{MULTIPUSH}\) needs \(\Theta(k)\) time, performing \(n\) \(\text{MULTIPUSH}\) operations, each with \(k\) elements, would take \(\Theta(kn)\) time, leading to amortized cost of \(\Theta(k)\).

17.1-2

Show that if a \(\text{DECREMENT}\) operation were included in the \(k\)-bit counter example, \(n\) operations could cost as much as \(\Theta(nk)\) time.

The logarithmic bit flipping predicate does not hold, and indeed a sequence of events could consist of the incrementation of all \(1\)s and decrementation of all \(0\)s; yielding \(\Theta(nk)\).

17.1-3

Suppose we perform a sequence of \(n\) operations on a data structure in which the \(i\)th operation costs \(i\) if \(i\) is an exact power of \(2\), and \(1\) otherwise. Use aggregate analysis to determine the amortized cost per operation.

Let \(n\) be arbitrary, and have the cost of operation \(i\) be \(c(i)\). Then we have,

\[ \begin{aligned} \sum_{i = 1}^n c(i) & = \sum_{i = 1}^{\left\lceil\lg n\right\rceil} 2^i + \sum_{i \le n \text{ is not a power of } 2} 1 \\\\ & \le \sum_{i = 1}^{\left\lceil\lg n\right\rceil} 2^i + n \\\\ & = 2^{1 + \left\lceil\lg n\right\rceil} - 1 + n \\\\ & \le 2n - 1 + n \\\\ & \le 3n \in O(n). \end{aligned} \]

To find the average, we divide by \(n\), and the amortized cost per operation is \(O(1)\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用