Amortized Complexity

This page introduces the basics of amortized complexity.

Introduction

Amortized Analysis is a technique used to analyze the performance of algorithms and dynamic data structures. It not only focuses on the cost of a single operation but also provides a more accurate assessment of overall performance by evaluating the average cost of a series of operations. Amortized analysis does not involve probability and only guarantees the average time per operation in the worst-case scenario; it does not confirm the average performance of the system. In the worst case, amortized analysis ensures that the average cost of all operations remains within a reasonable range by spreading the overhead of high-cost operations across low-cost operations.

Amortized analysis typically employs three main analytical methods: aggregate analysis, accounting method, and potential method. These methods each have their own focus and are suitable for different scenarios, but their common goal is to optimize the overall performance of data structures in the worst case by balancing operation costs.

Content

Consider an extensible array, such as vector in C++, with an initial capacity of \(m = 1\). Each time a new element is inserted, if the array is full, the size of the array must be doubled, the elements from the original array must be copied to the new array, and finally, the new element is inserted.

Next, using the insertion operation of a dynamic array as an example, we will analyze its amortized cost through three methods: aggregate analysis, accounting method, and potential method.

Aggregate Analysis

Aggregate Analysis calculates the total cost of a series of operations and averages it over each operation to derive the amortized time complexity per operation.

Taking the dynamic array as an example, we first identify two key costs of the insertion operation:

• If the array is not full, the cost of insertion is \(O(1)\).
• If the array is full, the insertion operation requires expansion, and the cost of copying elements after expansion is \(O(m)\), where \(m\) is the current size of the array.

Thus, to calculate the total cost of \(n\) insertion operations, we can break it down into two parts:

1. Cost of insertion operations: The direct cost of inserting each new element is constant time \(O(1)\). For \(n\) operations, the total cost is \(O(n)\).
2. Cost of array expansion: Each expansion involves copying elements from the original array to the new array. These operations occur when the array size is \(1, 2, 4, \ldots , 2^k\), where \(2^k\) is the largest power less than or equal to \(n\). The costs of expansion operations are \(1, 2, 4, \ldots , 2^{k-1}\), summing to \(1 + 2 + 4 + \ldots + 2^{k-1} = 2^k - 1\), which is the sum of a geometric series, resulting in \(O(n)\).

Therefore, the total insertion cost for the array is \(O(n)\), and the amortized cost per operation is \(O(1)\). Even in the worst case, the average cost per insertion operation remains constant time.

Accounting Method

The Accounting Method ensures that the total cost of all operations does not exceed the sum of pre-allocated amortized costs by assigning a fixed amortized cost to each operation in advance. The accounting method resembles a prepaid expense mechanism, where lower-cost operations store part of their cost to pay for future high-cost operations.

Taking the dynamic array as an example, we can assign a fixed amortized cost to each insertion operation to ensure sufficient funds are reserved for future expansions.

1. Cost allocation:

   • Assume the actual cost of each insertion operation is \(1\), and the amortized cost is set to \(3\).
   • Of this, \(1\) is used for the current insertion operation, and \(2\) is reserved for potential future expansion operations.

2. Cost usage:

   • When the array is full, an expansion operation is required, with an actual cost of \(O(m)\), where \(m\) is the current size of the array.
   • Suppose the number of elements in the array before expansion is \(n\). Since the latter half of the original array's \(n/2\) elements collectively pre-stored \(n\) units of amortized cost during insertion, this is exactly enough to cover the cost of the expansion operation.

Here is a concrete example:

Initial state:
arr    = [1, 2, 3, 4]  // initial array
amount = [2, 2, 2, 2]  // pre-stored cost for each element

// First expansion: array is full, needs expansion
arr    = [1, 2, 3, 4, null, null, null, null]  // array after expansion
amount = [2, 2, 0, 0, 0, 0, 0, 0]  // cost from 3, 4 used to pay for expansion

// Continue inserting new elements until full again
arr    = [1, 2, 3, 4, 5, 6, 7, 8]  // continue filling the array
amount = [2, 2, 0, 0, 2, 2, 2, 2]  // newly inserted elements also pre-store cost

// Second expansion: array is full again, needs larger space
arr    = [1, 2, 3, 4, 5, 6, 7, 8, null, null, null, null, null, null, null, null]  // array after expansion
amount = [2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]  // cost from 5, 6, 7, 8 used to pay for expansion

The above process shows that the amortized cost stored by each insertion operation is sufficient to pay for future expansion operations, ensuring that the amortized cost per operation remains \(O(1)\).

Potential Method

The Potential Method defines a potential function (usually denoted as \(\Phi\)) to measure the potential energy of a data structure, i.e., the reserved resources in the system state that can be used to pay for future high-cost operations. Changes in potential are used to balance the total cost of the operation sequence, ensuring that the amortized cost of the entire algorithm remains within a reasonable range.

Principle

First, define a state \(S\) as the state of the data structure at a given moment, which may include information such as the number of elements, capacity, pointers, etc. The initial state is defined as \(S_0\), i.e., the state before any operations are performed.

Second, define a potential function \(\Phi(S)\) to measure the potential energy of the data structure state \(S\), satisfying the following two properties:

1. Initial potential: In the initial state \(S_0\) of the data structure, the potential \(\Phi(S_0) = 0\).
2. Non-negativity: In any state \(S\), the potential \(\Phi(S) \geq 0\).

For each operation, its amortized cost \(\hat{c}\) is defined as:

\[ \hat{c} = c + \Phi(S') - \Phi(S) \]

where \(c\) is the actual cost of the operation, and \(S\) and \(S'\) represent the states of the data structure before and after the operation, respectively. This formula indicates that the amortized cost equals the actual cost plus the change in potential. If the operation increases the potential (i.e., \(\Phi(S') > \Phi(S)\)), the amortized cost rises; if the operation consumes potential (i.e., \(\Phi(S') < \Phi(S)\)), the amortized cost decreases.

We can analyze the total cost of a series of operations using the potential function. Let \(S_1, S_2, \dots, S_m\) be the sequence of states generated from the initial state \(S_0\) after \(m\) operations, and let \(c_i\) be the actual cost of the \(i\)-th operation. Then the amortized cost \(p_i\) of the \(i\)-th operation is:

\[ p_i = c_i + \Phi(S_i) - \Phi(S_{i-1}) \]

Therefore, the total time cost of \(m\) operations is:

\[ \sum_{i=1}^m c_i = \sum_{i=1}^m p_i + \Phi(S_0) - \Phi(S_m) \]

Since \(\Phi(S) \geq \Phi(S_0)\), the upper bound of the total time cost is:

\[ \sum_{i=1}^m p_i \geq \sum_{i=1}^m c_i \]

Thus, if \(p_i = O(T(n))\), then \(O(T(n))\) is an upper bound for the amortized complexity.

Example: Expansion Analysis of Dynamic Array

Taking the insertion operation of a dynamic array vector as an example, define the following potential function \(\Phi(h)\):

\[ \Phi(h) = 2n - m \]

where \(n\) is the number of elements in the array, and \(m\) is the current capacity of the array. This potential function reflects the amount of remaining available space in the array, i.e., the difference between the current capacity and the actual used space.

1. Insertion operation (no expansion required):

   • Operation cost: \(O(1)\), as only one element needs to be inserted.
   • Potential change: After insertion, the number of elements increases by 1, and the potential increases by \(2\).
     • \(\Phi(h') - \Phi(h) = 2(n + 1) - m - (2n - m) = 2\)
   • Amortized cost: \(1 + 2 = 3\)

2. Insertion operation (triggering expansion):

   • Assume the current capacity \(m = n\). Inserting a new element triggers expansion, and the new capacity becomes \(2n\).
   • Operation cost: \(O(n)\), as all elements need to be copied to the new array, and the new element is inserted.
   • Potential change: After expansion, the capacity increases, and the potential decreases by \(2 - n\).
     • \(\Phi(h') - \Phi(h) = 2(n + 1) - 2n - (2n - n) = 2 - n\)
   • Amortized cost: \(n + 1 + (2 - n) = 3\)

From the above analysis, it can be seen that although the actual cost of the expansion operation is high, due to the design of the potential function, the overall amortized cost remains at a constant level \(O(1)\).

Extended Example: Stack Operations

Stack operations are a classic application scenario for amortized analysis. Suppose stack S supports the following three operations:

Operation	Description	Actual Cost \(c_i\)
S.push(x)	Push element x onto stack	\(1\)
S.pop()	Pop the top element	\(1\)
S.multi-pop(k)	Pop top k elements	\(O(\min{\lvert S\rvert, k})\)

We will analyze the amortized cost of these stack operations using three methods: aggregate analysis, accounting method, and potential method.

Aggregate Analysis

Aggregate analysis calculates the total cost of all operations and averages it over each operation to derive the amortized cost.

1. For \(n_{push}\) push(x) operations, each costs \(O(1)\), so the total cost is \(O(n_{push})\).
2. For \(n_{pop}\) pop() operations, each costs \(O(1)\), so the total cost is \(O(n_{pop})\).
3. For \(n_{multi-pop}\) multi-pop(k) operations, although the actual cost of each is \(O(\min(\lvert S \rvert, k))\), the total number of elements popped by these operations cannot exceed the number of elements previously pushed by push(x), so the total cost is still bounded by \(n_{push}\).

Since the total number of operations \(n = n_{push} + n_{pop} + n_{multi-pop} \leq 2 \times n_{push}\), the total cost is \(O(n_{push}) = O(n)\), and the amortized cost per operation is \(O(n)/n = O(1)\).

Accounting Method

The accounting method reserves part of the cost for each push(x) operation to pay for future possible pop() or multi-pop(k) operations.

1. S.push(x): Assume the amortized cost of each push(x) operation is \(2\), where \(1\) unit is used for the current operation, and the other \(1\) unit is stored as credit to pay for future pop() or multi-pop(k) operations.
2. S.pop(): The actual cost is \(1\), but since the previous push(x) operation has pre-stored \(1\) unit of credit for it, the amortized cost is \(0\).
3. S.multi-pop(k): The actual cost of each popped element is \(1\), which can be paid by the credit pre-stored by the push(x) operation of that element, so the amortized cost is \(0\).

From the above analysis, the credit pre-stored by the push operation is sufficient to pay for the future pop operation of that element, so the amortized cost per operation is \(O(1)\).

Potential Method

The potential method defines a potential function to measure the state of the stack and uses changes in potential to balance operation costs.

1. Potential function: Let \(\Phi(h)\) be the number of elements in the stack, i.e., \(\Phi(h) = \lvert S \rvert\). Each element contributes \(1\) unit of potential.
2. S.push(x): Each push(x) operation increases the number of elements in the stack, increasing the potential by \(1\), so the amortized cost is \(1 + 1 = 2\).
3. S.pop(): Each pop() operation decreases the number of elements in the stack, decreasing the potential by \(1\), so the amortized cost is \(1 - 1 = 0\).
4. S.multi-pop(k): The multi-pop(k) operation pops \(k\) elements, decreasing the potential by \(k\), so the amortized cost is \(k - k = 0\).

With the above potential function design, the amortized cost of push(x) is \(2\), while the amortized cost of pop() and multi-pop(k) is \(0\). Therefore, the amortized cost of all stack operations is \(O(1)\).

References

• Amortized Analysis - Wikipedia
• Cornell CS 3110 - Lecture 20: Amortized Analysis

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用