Skip to content

Amortized Analysis

Target

Any M consecutive tree operations starting from an empty tree take at most \(O(M \log N)\) time.

We have this: $$ worst\; case\; bound \geq amortized\; bound \geq average \; case\; bound $$

Aggregate Analysis(总量分析)

Idea

image-20240917133457666

Accounting method(会计法)

image-20240917141031263

Notice that：

image-20240917141201082

Ex: Stack with MultiPop

image-20240917141722891

BUT: The most difficult part of amortized method is to guess the amortized cost

Potential method(势能法)

Idea

image-20240917142147461

  • 所以究竟什么是信用？信用是这个操作把问题结构改变了多少

image-20240917142836925

  • we have to guess a good potantial function for the current problem structure
  • So a good potential function requires that the first element \(\phi(D_0)\)

Ex: Stack with MultiPop(int k, Stack S)

image-20240917144158959

Ex: Splay Trees

image-20240917145515661

image-20240917145615208 $$ \hat{c_i} \leq 1+3(R_2(X)-R_1(X)) $$

  • 所以总和最大就是\(1+3(R_N(X)-R_1(X))\)，也就是\(O(\log N)\)

Problem

1

When doing amortized analysis, which one of the following statements is FALSE?

image-20240917152122823

B

The "maximum" is wrong, it should be "minimum".

2

image-20240917190833469

A. The number of items currently in the buffer

B. The opposite number of items currently in the buffer

C. The number of available blocks currently in the buffer

D. The opposite number of available blocks in the buffer

D

image-20240917190918369