CS计算机代考程序代写 data structure Amortized Analysis

Amortized Analysis

Operations don’t stand alone!

Often, we perform _________ of operations on data structures
and we are interested in the time complexity of the
__________________

Definition: worst-case sequence complexity (WCSC)

WCSC m * worst-case time complexity of any one operation
in a sequence of m operations

Amortized Sequence Complexity

Definition: amortized sequence complexity

• Represents the “average” worst-case complexity of each
operation

• Different than average-case time (no probability!)
• Often makes more sense in real situation

Approaches to Calculating Amortized Complexity

• Aggregate

• Accounting

• Potential

Binary Counters (from CS Unplugged)
CS Unplugged video

Fun Video

Binary Counters
Suppose we are counting up with a binary counter:

when does the 1’s digit get flipped?
when does the 2’s digit get flipped?
what about the 4’s digit?

Zoom Chat

Binary Counter: Aggregate Approach
Initial counter 00000 Value = 0

After INCREMENT 00001 Value = 1 Cost = 1

After INCREMENT 00010 Value = 2 Cost =

After INCREMENT Value = 3 Cost =

After INCREMENT Value = 4 Cost =

After INCREMENT Value = 5 Cost =

After INCREMENT Cost =

After INCREMENT Cost =

After INCREMENT Cost =

After INCREMENT Cost =

After INCREMENT Cost =

Chalk Talk

Binary Counter = sequence of k
bits (k fixed) with single
operation: INCREMENT

Chalk Talk

Chalk Talk

Multipop Stack

• A stack with the regular PUSH and POP operations
• Each take O(1) time

Worksheet Multipop Stack: Aggregate Approach

Accounting Approach

Charge each operation an amortized cost


When amortized cost > actual cost

When amortized cost < actual cost • Can NEVER be in debt Chalk Talk Accounting Approach: Multipop Stack Binary Counter: Aggregate Approach Initial counter 00000 Value = 0 After INCREMENT 00001 Value = 1 Cost = 1 After INCREMENT 00010 Value = 2 Cost = After INCREMENT Value = 3 Cost = After INCREMENT Value = 4 Cost = After INCREMENT Value = 5 Cost = After INCREMENT Cost = … After INCREMENT Cost = After INCREMENT Cost = After INCREMENT Cost = After INCREMENT Cost = Worksheet Binary Counter = sequence of k bits (k fixed) with single operation: INCREMENT Worksheet Accounting Approach: Binary Counter Dynamic Arrays: Reminder Dynamic Arrays: Copying ElementsChalk Talk Worksheet Dynamic Arrays: Accounting method Worksheet Dynamic Arrays: Aggregate method Worksheet Dynamic Arrays: Aggregate method