第三十七课: Amortized Analysis

虽然 average method 很方便的衡量了 insert()操作的平均时间，但 average method 没法处理和估计 delete() 的时间，因为你通过 insert()增加元素，通过 delete()减少元素，两者可以有无数种组合，没法把他们都加起来然后平均。

Suppose every operation (insert, find, remove) takes one dollar of actual running time unless the hash table is resized. We resize the table in two circumstances.

• An insert operation doubles the table size if n = N AFTER the new item is inserted and n is incremented, taking 2N additional dollars of time for resizing to 2N buckets. Thus, the load factor is always less than one.
• The remove operation halves the table size if n = N/4 AFTER the item is deleted and n is decremented, taking N additional dollars of time for resizing to N/2 buckets. Thus, the load factor is always greater than 0.25 (except when n = 0, i.e. the table is empty).

Either way, a hash table that has just been resized has n = N/2. A newly constructed hash table has n = 0 items and N = 1 buckets.

By trial and error, I came up with the following amortized costs.

insert:  5 dollars
remove:  5 dollars
find:    1 dollar
为什么 find cost 很少，因为他永远不会 resize hashtable

value of n and N when start accouting

    下面的事情就是来验证，我们对 api()消耗所做出的猜测是否正确
    假设 n 和 N 是当 hashtable 为空或者刚刚 resize 后的值
             这里的假设就和 average method 不一样，average method 是假设一切从零开始，hashtable
             一开始也是空的，慢慢插入;
             accounting method 假设是 empty or just resized，空或者刚刚被 resize 过。

    这样假设之后，n 在每一次开始时（empty or just resized）
    都处在[N/2 - 1, N/2 + 1]之间, 注意这里的 N 是经过 resize 之后的 hashtable 大小。
             比如，一开始 N = 8, n = 8
             insert(), ==> N = 8*2 = 16, n = 8 + 1 = 9
                       ==> n = 16/2 + 1 = _N/2 + 1_;
             比如，一开始 N = 8, n = 2
             delete(), ==> N = 8/2 =4,   n = 2 - 1 = 1
                       ==> n = 4/2 -1   = _N/2 - 1_;

our target

最重要的是通过这个公式，我们不用知道之前操作的时间消耗(combination of series of operations)，我们可以直接通过现在的 n 和 N 估算出目前银行里存有多少 dollars。只要我们可以估算出，in a long term, 银行里的前不会小于 0（实际时间消耗 < 估算时间消耗）,即可。

We charge an amortized $5 for an insert or remove operation. Every insert or remove operation costs one actual dollar (not counting resizing) and puts the remaining $4 in the bank to pay for resizing. For every step n takes away from N/2, we accumulate another $4.

So, when encount a 'resize', there must be at least 4*|n - N/2| dollars saved (or 4n dollars for a never-resized one-bucket hash table).

An insert operation only resizes the table if the number of items n reaches N. According to the formula 4|n - N/2|, there are at least 2N dollars in the bank.

Resizing the hash table from N to 2N buckets costs 2N dollars, so we can afford it.

After we resize, the bank balance might be zero again, but it isn't negative.

比如，一开始 N = 9, n = 16

|------------------------------+-------------------+-----+----|----\
| insert(), ==> n = 10, N = 16 | actual_cost = 1$  |     |    |    |
|                              | amortized   = 5$  |   4 |  4 |    |
|------------------------------+-------------------+-----+----|    |
| insert(), ==> n = 11, N = 16 | actual_cost = 1$  |     |    |    |
|                              | amortized   = 5$  |   4 |  8 |    |
|------------------------------+-------------------+-----+----|    |
| insert(), ==> n = 12, N = 16 | actual_cost = 1$  |     |    |    |
|                              | amortized   = 5$  |   4 | 12 |    |> <<store dollars>>   |
|------------------------------+-------------------+-----+----|    |                      |
| insert(), ==> n = 13, N = 16 | actual_cost = 1$  |     |    |    |                      |
|                              | amortized   = 5$  |   4 | 16 |    |                      |
|------------------------------+-------------------+-----+----|    |                      |
| insert(), ==> n = 14, N = 16 | actual_cost = 1$  |     |    |    |                      |
|                              | amortized   = 5$  |   4 | 20 |    |                      |> 一轮一轮的看,整体 dollars 总是>0
|------------------------------+-------------------+-----+----|    |                      |
| insert(), ==> n = 15, N = 16 | actual_cost = 1$  |     |    |    |                      |
|                              | amortized   = 5$  |   4 | 24 |    |                      |
|------------------------------+-------------------+-----+----|    |                      |
| insert(), ==> n = 16, N = 16 | actual_cost = 1$  |     |    |    |                      |
|                              | amortized   = 5$  |   4 | 28 |----/                      |
|------------------------------+-------------------+-----+----|                           |
| insert(), ==> n = 17, N = 32 | actual_cost = 32$ | -27 |  1 |----> <<withdraw dollars>> |
|                              | amortized   = 5$  |     |    |

4|n - N/2| 这里的 n 是指在 N/2+1 ~ N 之间游走时，会一直[[store dollars]]。
当 n = N+1 的时候开始 [[withdraw dollars]]


当 n = N+1, 会导致 N-->2N, 这里重新分配一个 2N 大小的数组，消耗 2N dollars 时间。
但我总体来看，一轮一轮的看，银行里的 dollars 不会小于 0,所以 amortized 估计总是大于 actual
所以：
       insert:  5 dollars
       remove:  5 dollars
       find:    1 dollar
是合理的。

IMPORTANT: Note that 4|n - N/2| is a function of the data structure, and does NOT depend on the history of hash table operations performed.

The crucial insight is that at any time, we can look at a hash table and know a lower bound for how many dollars are in the bank from the values of n and N.

In general, the accounting method only works if you can tell how much money is in the bank (or, more commonly, a minimum bound on that bank balance) just by looking at the current state of the data structure–without knowing how the data structure reached that state.

We know that the last time the hash table was resized, the number of items n was exactly N/2. So if n != N/2, there have been subsequent insert/remove operations, and these have put money in the bank.

A remove operation only resizes the table if the number of items n drops to N/4. According to the formula 4|n - N/2|, there are at least N dollars in the bank. Resizing the hash table from N to N/2 buckets costs N dollars, so we can afford it.

The bank balance never drops below zero, so my amortized costs above are valid. Therefore, the amortized cost of all three operations is in O(1).

Observe that if we alternate between inserting and deleting the same item over and over, the hash table is never resized, so we save up a lot of money in the bank. This isn't a problem; it just means the algorithm is faster (spends fewer dollars) than my amortized costs indicate.