17.2 The accounting method

17.2-1

Suppose we perform a sequence of stack operations on a stack whose size never exceeds $k$. After every $k$ operations, we make a copy of the entire stack for backup purposes. Show that the cost of $n$ stack operations, including copying the stack, is $O(n)$ by assigning suitable amortized costs to the various stack operations.

For every stack operation, we charge twice.

First, we charge the actual cost of the stack operation.
Second, we charge the cost of copying an element later on.

Since we have the size of the stack never exceed $k$, and there are always $k$ operations between backups, we always overpay by at least enough. Therefore, the amortized cost of the operation is constant, and the cost of the $n$ operation is $O(n)$.

17.2-2

Redo Exercise 17.1-3 using an accounting method of analysis.

Let $c_i =$ cost of $i$th operation.

\[ c_i = \begin{cases} i & \text{if $i$ is an exact power of $2$}, \\\\ 1 & \text{otherwise}. \end{cases} \]

Charge $3$ (amortized cost $\hat c_i$) for each operation.

If $i$ is not an exact power of $2$, pay $\$1$, and store $\$2$ as credit.
If $i$ is an exact power of $2$, pay $\$i$, using stored credit.

\[ \begin{array}{cccc} \text{Operation} & \text{Cost} & \text{Actual cost} & \text{Credit remaining} \\\\ \hline 1 & 3 & 1 & 2 \\\\ 2 & 3 & 2 & 3 \\\\ 3 & 3 & 1 & 5 \\\\ 4 & 3 & 4 & 4 \\\\ 5 & 3 & 1 & 6 \\\\ 6 & 3 & 1 & 8 \\\\ 7 & 3 & 1 & 10 \\\\ 8 & 3 & 8 & 5 \\\\ 9 & 3 & 1 & 7 \\\\ 10 & 3 & 1 & 9 \\\\ \vdots & \vdots & \vdots & \vdots \end{array} \]

Since the amortized cost is $\$3$ per operation, $\sum\limits_{i = 1}^n \hat c_i = 3n$.

We know from Exercise 17.1-3 that $\sum\limits_{i = 1}^n \hat c_i < 3n$.

Then we have

\[\sum_{i = 1}^n \hat c_i \ge \sum_{i = 1}^n c_i \Rightarrow \text{credit} = \text{amortized cose} - \text{actual cost} \ge 0.\]

Since the amortized cost of each operation is $O(1)$, and the amount of credit never goes negative, the total cost of $n$ operations is $O(n)$.

17.2-3

Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in it $0$). Counting the time to examine or modify a bit as $\Theta(1)$, show how to implement a counter as an array of bits so that any sequence of $n$ $\text{INCREMENT}$ and $\text{RESET}$ operations takes time $O(n)$ on an initially zero counter. ($\textit{Hint:}$ Keep a pointer to the high-order $1$.)

(Removed)

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