분할 상환 분석과 동적 배열의 구현

작성일 | In

0. 목차

  1. 분할 상환 분석
  2. 동적 배열의 구현
  3. 포텐셜 메소드
  4. 동적 배열의 시간 복잡도 분석

1. 분할 상환 분석

1-1. 대출 상환 방식의 종류

대출을 갚는 방법은 여러 가지가 있지만, 일단 이 글에서는 만기 일시 상환과 원리금 균등 분할 상환에 주목해 봅시다. 만기 일시 상환은 대출받은 뒤 만기일 전까지는 이자만 갚다가 만기 때 남은 이자와 대출 원금을 갚는 방식입니다. 평소에는 조금씩 돈을 갚다가 마지막에 한 번 큰 금액을 갚는다고 생각하면 됩니다. 원리금 균등 분할 상환은 (대출 원금 + 만기일까지 지급해야 할 이자)를 만기일까지 균등하게 상환하는 방식입니다. 같은 금액을 갚는 것이지만(사실은 조금 다릅니다) 조금씩 갚다가 딱 한 번 많이 갚는 것과, 매번 균등하게 갚는 차이가 있습니다.

알고리즘 세미나에서 왜 뜬금없이 대출 이야기를 하는지 궁금한 분들이 있을 텐데, 그 이유는 뒷 내용을 들으면 자연스럽게 이해가 될 것입니다.

1-2. worst time complexity의 함정 (1)

BOJ 31218 자료 구조의 왕 문제를 봅시다. 이 문제에서 요구하는 것을 아래 코드와 같이 구현하면 각 쿼리를 $O(\max(N,M))$ 시간에 처리할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int N, M, Q, A[1010][1010], C;
bool Bound(int i, int j){ return 1 <= i && i <= N && 1 <= j && j <= M; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> Q;
    for(int q=1; q<=Q; q++){
        int op, di, dj, i, j; cin >> op;
        if(op == 1){
            cin >> di >> dj >> i >> j;
            while(Bound(i, j) && !A[i][j]) A[i][j] = 1, C++, i += di, j += dj;
        }
        if(op == 2) cin >> i >> j, cout << A[i][j] << "\n";
        if(op == 3) cout << N * M - C << "\n";
    }
}

각 쿼리를 처리하는데 $O(\max(N,M))$ 시간이 걸리므로 전체 시간 복잡도는 $O(Q \max(N, M))$입니다. 시간 복잡도만 보면 약 2억 번의 연산을 수행해서 시간제한 안에 간당간당하게 들어와야 할 것 같지만, 실제로 위 코드를 제출해 보면 64ms 정도로 매우 빠르게 동작하는 것을 확인할 수 있습니다. $O(Q\max(N,M))$이라는 수식이 이 프로그램의 연산량을 정확하게 나타내고 있지 않다는 것을 유추할 수 있습니다.

코드의 14번째 줄에 있는 while문이 실제로 얼마나 반복하게 될지 생각해 봅시다. while문 내부의 코드는 $(i, j)$가 잔디밭 내부에 있으면서 아직 그 위치에 잔디가 있을 때만 동작하고, 만약 $(i, j)$가 잔디밭 밖으로 나가거나 그 위치에 잔디가 없으면 반복을 중단합니다. 따라서 while문은 마지막 비교를 제외하면 잔디밭의 넓이보다 더 많이 반복할 수 없습니다. 그러므로 위 프로그램의 시간 복잡도는 $O(Q\max(N,M))$ 대신 $O(NM+Q)$으로도 표현할 수 있습니다.

1-3. worst time complexity의 함정 (2)

BOJ 17298 오큰수 문제를 봅시다. 이 문제는 스택을 이용해 아래 코드와 같이 해결할 수 있음이 잘 알려져 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int N, A[1010101], B[1010101];

void pop_leq_k(stack<int> &stk, int k){
    while(!stk.empty() && stk.top() <= k) stk.pop();
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];

    stack<int> S;
    for(int i=N; i>=1; i--){
        pop_leq_k(S, A[i]);
        B[i] = S.empty() ? -1 : S.top();
        S.push(A[i]);
    }
    for(int i=1; i<=N; i++) cout << B[i] << " ";
}

이 코드는 스택에서 $k$보다 작거나 같은 원소를 모두 제거하는 pop_leq_k 연산을 $N$번 수행합니다. pop_leq_k 연산의 시간 복잡도는 얼마나 될까요? 스택 $S$에 최대 $N$개의 원소가 있을 수 있기 때문에 한 번의 pop_leq_k 연산에서 최대 $N$개의 원소를 제거할 수 있습니다. 따라서 pop_leq_k의 시간 복잡도는 $O(N)$이고, 위 프로그램은 이러한 연산을 $N$번 수행하므로 전체 시간 복잡도는 $O(N^2)$입니다. 이상한 점이 보이나요?

시간 복잡도를 다시 계산해 봅시다. 위 프로그램에서 스택을 빠져나온 원소가 다시 스택에 들어가는 일은 발생하지 않습니다. 즉, 각 원소를 정확히 한 번 스택에 들어간 뒤, 최대 한 번 스택을 빠져나옵니다. 따라서 전체 시간 복잡도는 $O(N)$입니다.

$N$개의 답을 구하는 동안 수행하는 전체 연산 횟수가 $O(N)$인 점을 생각하면, pop_leq_k 연산의 시간 복잡도를 $O(N)$이라고 하는 것은 별로 좋은 표현이 아닌 것처럼 느껴집니다. 그렇다고 $O(1)$이라고 하는 건 올바른 표현이 아닙니다. pop_leq_k 연산의 시간 복잡도를 어떻게 표현하는 것이 좋을까요?

1-4. 분할 상환 분석

분할 상환 분석은 이런 질문에 대한 멋진 답을 알려줄 수 있습니다. 다시 대출 이야기로 돌아가 봅시다. 오큰수 문제의 pop_leq_k 연산은 $k$가 스택에 있는 원소들에 비해 상대적으로 작을 때 적은 금액을 갚고, $k$가 클 때는 많은 금액을 갚는 것으로 생각할 수 있습니다. 우리는 $N$번의 연산을 수행하는데 총 $O(N)$ 시간이 걸린다는 것을 알고 있기 때문에, 대출을 균등 분할 상환 방식으로 갚으면 매번 $O(1)$ 만큼만 갚아도 된다는 것을 알 수 있습니다. 그러므로 우리는 앞으로 오큰수 문제에서 pop_leq_k 연산의 시간 복잡도를 amortized $O(1)$로 나타낼 것입니다.

이는 평균 시간 복잡도 분석과는 분명히 다릅니다. 평균 시간 복잡도 분석은 확률을 이용해 분석한 것이기 때문에 Big-O notation으로 나타낸 것보다 더 많은 연산이 발생할 수 있지만, 분할 상환 분석은 확률이 포함되지 않았기 때문에 최악의 경우에도 각 연산의 평균 수행 시간을 보장합니다. 퀵 정렬의 평균 시간 복잡도는 $O(N \log N)$이고 $O(N^2)$에 동작하도록 하는 입력을 쉽게 만들 수 있지만, $N$번의 pop_leq_k 연산이 $O(N)$보다 더 많은 연산을 수행하도록 하는 입력은 절대 만들 수 없습니다.

분할 상환 분석을 하는 방법은 여러가지가 있는데, 이 문단에서 총계 분석(aggregate method), 결산 분석(accounting method)을, 뒤에 3장에서 잠재 비용 분석(potential method)에 대해 설명합니다.

총계 분석은 $n$번의 연산을 수행하는데 $T(n)$ 시간이 걸렸다면 연산 한 번의 시간 복잡도를 amortized $T(n) / n$으로 표현하는 방법으로, 위에서 오큰수 문제의 시간 복잡도를 분석할 때 사용한 방법입니다. 자료 구조의 왕 문제는 $Q$개의 쿼리를 처리하는 데 $O(NM+Q)$ 만큼의 시간이 소요되므로 쿼리 한 번의 시간 복잡도는 amortized $O(NM/Q+1)$ 이라고 나타낼 수 있습니다.

결산 분석은 각 연산의 분할 상환 비용 $\hat{c}_i$를 미리 정한 다음, 연산의 실제 비용 $c_i$가 $\hat{c}_i$보다 작은 경우 $\hat{c}_i - c_i$를 저장하는 방식으로 분석을 진행합니다. 즉, 분할 상환 비용보다 더 적은 비용을 사용했다면, 그 차액을 저축한 다음 나중에 더 오래걸리는 연산을 수행하는 데 사용하는 것입니다. 이 방법은 총계 분석과 다르게 연산종류마다 분할 상환 비용을 다르게 설정할 수 있습니다.

몇 가지 제약 사항이 있는데, $N$번의 연산을 수행할 때의 분할 상환 비용은 실제 비용보다 크거나 같아야 합니다. 즉, $\sum_{i=1}^N \hat{c}_i \geq \sum_{i=1}^{N} c_i$를 충족해서 실제 비용의 상한을 나타낼 수 있어야 합니다. 또한, 매 순간에도 $\sum_{i=1}^{k} (\hat{c}_i - c_i) \geq 0$을 만족해야 합니다. 만약 연산 수행 도중에 값이 0보다 작아지게 된다면, 그 시점까지 투입된 비용의 상한을 나타낼 수 없기 때문입니다.

오큰수 문제를 다시 살펴봅시다. S.push(x)를 수행할 때의 분할 상환 비용을 2, pop_leq_k를 수행할 때의 분할 상환 비용을 0으로 설정하겠습니다. 프로그램은 S.push(x)를 수행할 때마다 1 만큼의 비용을 저축하고, pop_leq_k에서 pop된 원소의 개수만큼 저축한 비용을 사용합니다. 즉, 저축된 금액은 스택의 크기와 동일합니다. 따라서 위에서 언급한 두 조건을 모두 만족하는 것을 알 수 있습니다. 따라서 S.push(x)를 $N$번, pop_leq_k를 $M$번 수행했을 때의 시간 복잡도는 $2N \in O(N)$으로 나타낼 수 있습니다.

2. 동적 배열의 구현

2-1. 문제 소개

동적 배열은 C++의 std::vector처럼 들어있는 원소의 개수에 따라 크기가 유동적으로 변하는 배열을 의미합니다. 이 글에서는 push_back 연산과 pop_back 연산을 지원하는 동적 배열을 구현하면서, 잠재 비용 분석(potential method) 방법을 이용해 시간 복잡도를 분석하는 방법에 대해 다룹니다.

동적 배열은 미리 공간을 여유 있게 할당한 다음, 배열에 데이터를 저장할 때마다 미리 할당받은 공간에 하나씩 저장하는 방식으로 동작합니다. 만약 할당받아 놓은 공간을 모두 사용했다면, 조금 더 큰 공간을 할당받은 다음, 기존에 저장되어 있던 데이터를 모두 새로운 공간으로 옮긴 이후에 데이터를 추가합니다. 따라서 동적 배열은 현재 저장되어 있는 데이터의 개수를 나타내는 변수인 size와 할당받은 공간의 크기를 나타내는 변수인 capacity를 관리해야 합니다.

미리 할당받은 공간에 데이터를 저장하는 것은 단순히 arr[size++] = data;와 같이 상수 시간에 처리할 수 있고, pop_back 연산도 size--;를 이용해 상수 시간에 처리할 수 있습니다. 따라서 동적 배열의 성능은 할당받은 공간을 모두 사용했을 때 추가 공간을 할당하는 정책에 따라 결정된다고 볼 수 있습니다.

2-2. 재할당 정책에 따른 성능

가장 먼저 생각나는 방법은 아마 적당한 상수 $B$을 잡은 뒤, 공간이 가득 찼을 때마다 $B$ 만큼의 공간을 추가로 할당하는 방법일 것입니다. $n$번의 삽입에서 필요한 총 연산 횟수를 계산해 봅시다. $n = kB+1$번째 삽입에서는 기존에 저장되어 있던 데이터를 복사하는 데 $O(n)$ 만큼의 연산을 수행해야 하고, $n$번째 데이터를 저장하는 데 $O(1)$ 만큼의 연산을 추가로 수행합니다. $n \not\equiv 1 \pmod B$일 때는 $O(1)$ 만큼의 연산만 수행하면 됩니다.

$n = kB+1$ 꼴이면 원소를 $n$번 삽입할 때 $B(1+2+\cdots + k) + n \in O(Bk^2 + n)$ 만큼의 연산을 수행해야 합니다. $Bk \in O(n)$이므로 $O(nk)$으로 나타낼 수 있으며, $B$는 상수이므로 $k = n/B \in \Theta(n)$이 되어서 전체 시간 복잡도는 $O(n^2)$이 됩니다. $B$의 값을 크게 잡을수록 재할당 횟수가 적어지고 $k = n/B$의 크기도 줄어들어서 조금의 성능 개선이 있을 수 있겠지만, $n$이 충분히 크다면 $B$의 값에 관계없이 $O(n^2)$이 돼서 비효율적인 것은 여전합니다.

조금 더 공부를 해본 사람이라면 $B = \sqrt n$으로 정해서 전체 시간 복잡도를 $O(n \sqrt n)$으로 만드는 방법을 생각할 수도 있을 것입니다. 하지만 총 연산 횟수는 프로그램을 실행하는 시점에 알 수 없기 때문에 $n$을 이용해 $B$를 정하는 것은 불가능합니다. 더 좋은 방법은 없는 걸까요?

2-3. array doubling

매번 공간을 2배씩 확장하면 원소를 $n$번 삽입하는 것을 총 $3n$번의 연산만으로 처리할 수 있습니다. $n=2^k+1$번의 삽입에서 필요한 연산 횟수를 계산해 봅시다. 데이터를 저장하는 연산을 $n$번 수행해야 하고, 추가로 $2^0+1, 2^1+1, \cdots, 2^{k-1}+1, 2^k+1$번째 삽입에서 각각 $2^0, 2^1, \cdots, 2^{k-1}, 2^k$번의 복사를 수행해야 합니다. $2^0 + 2^1 + \cdots + 2^k = 2^{k+1}-1$이므로 $n = 2^k+1$번의 삽입에서 $3n-3$번의 연산을 수행해야 합니다. 따라서 매번 공간을 2배씩 확장할 때 push_back 연산의 시간 복잡도는 amortized $O(1)$이라는 것을 알 수 있습니다.

이 방법은 한 가지 문제점이 있습니다. pop_back을 여러 번 수행해서 더 이상 사용하지 않는 공간이 많이 남아있을 때에도 할당받은 공간을 해제하지 않기 때문에 공간을 낭비하게 됩니다. 할당받은 공간을 모두 사용했을 때 공간을 2배로 늘렸으니 pop_back으로 인해 capacity의 절반 이하를 사용할 때 공간의 크기를 절반으로 줄이는 방법은 어떨까요? 이 방법은 size와 capacity가 같은 상황에서 push_back과 pop_back을 번갈아 가며 호출하면 매번 $O(n)$의 연산을 수행하게 돼서 비효율적입니다.

할당받은 공간의 1/4 이하만 사용할 때 공간의 크기를 절반으로 줄이는 정책을 사용하면 삽입과 삭제를 $n$번 수행했을 때 최대 $O(n)$번의 연산만 한다는 것을 증명할 수 있습니다. 하지만 실제로 총계 분석이나 결산 분석 방법을 이용해 직접 증명하려고 하면 쉽지 않습니다. 이를 증명하는 건 뒤에서 포텐셜 메소드를 배운 뒤에 하도록 하고, 일단 지금은 amortized $O(1)$에 동작한다고 믿고 넘어갑시다.

2-4. 구현

(링크)

3. 포텐셜 메소드

3-1. 개요

포텐셜 메소드는 결산 분석과 비슷하게 미리 지불한 비용을 향후 연산에 사용하는 방식입니다. 하지만 결산 분석은 각 연산마다 선불 비용을 계산했다면, 포텐셜 메소드는 자료구조 전체 상태에 선불 비용을 달아놓는다는 점에서 차이가 있습니다.

자료구조의 초기 상태를 $D_0$, $D_{i-1}$에 $i$번째 연산을 적용한 자료구조의 상태를 $D_i$라고 합시다. 포텐셜 함수 $\Phi(D_i)$는 자료구조의 상태 $D_i$를 음이 아닌 실수로 보내는 함수로, 자료구조가 얼마나 많이 망가져 있는지를 나타냅니다. 이때 $i$번째 연산의 분할 상환 비용은 $\hat{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1})$, 즉 $i$번째 연산의 실제 비용과 $i$번째 연산으로 인해 자료구조가 지저분해진 정도를 더한 값으로 정의합니다. 다시 말해, $\Phi(D_i) - \Phi(D_{i-1}) > 0$이면 자료구조를 더럽히는 대신 미래를 위해 약간의 비용을 저축하는 것이고, $\Phi(D_i) - \Phi(D_{i-1}) < 0$이면 지금까지 저축한 것을 사용해 자료구조를 이상적인 형태로 보내는 것을 의미합니다.

$n$번의 연산을 모두 수행했을 때 분할 상환 비용의 합은 $\sum_{i=1}^{n} \hat{c}_i = \sum_{i=1}^{n} (c_i + \Phi(D_i) - \Phi(D_{i-1}))$이고, 식을 정리하면 $\sum_{i=1}^{n} \hat{c}_i = \sum_{i=1}^{n} c_i + \Phi(D_n) - \Phi(D_0)$이 됩니다. 결산 분석에서와 같이, $\Phi(D_0) = 0$으로 지정한 다음, 모든 $i$에 대해 $\Phi(D_i) \geq \Phi(D_0)$을 만족하도록 함수를 정의하면 분할 상환 비용의 합은 실제 비용의 상한이 됩니다.

3-2. BOJ 17298 오큰수

$\Phi(D)$를 스택에 있는 원소의 개수로 정의합시다. 처음에 $\Phi(D_0) = 0$이고, 원소의 개수가 음수가 될 수 없으므로 항상 $\Phi(D_i) \geq \Phi(D_0)$을 만족함을 알 수 있습니다. 스택에 $s$개의 원소가 있는 상황에서 S.push(x) 연산의 분할 상환 비용은 $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) = 1 + (s + 1) - s = 2$입니다. $s$개의 원소가 있는 상황에서 pop_leq_k 연산을 통해 $x$개의 원소를 삭제한 상황을 생각해 봅시다. 이때의 분할 상환 비용은 $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) = x + (s - x) - s = 0$입니다. 따라서 pop_leq_k 연산의 분할 상환 비용은 삭제하는 원소의 개수에 관계없이 항상 0입니다.

두 연산의 분할 상환 비용은 $O(1)$이기 때문에 연산을 $n$번 수행했을 때의 분할 상환 비용의 총합은 $O(n)$이고, $\Phi(D_i) \geq \Phi(D_0)$이기 때문에 분할 상환 비용의 총합은 실제 비용의 상한을 나타냅니다. 따라서 실제 연산 횟수는 $O(n)$을 넘지 않음을 알 수 있습니다.

3-3. push_back만 수행하는 동적 배열

push_back과 pop_back을 모두 지원하는 동적 배열의 시간 복잡도를 분석하기 전에, 조금 더 간단한 케이스인 push_back만 지원하는 동적 배열의 시간 복잡도를 분석해 보겠습니다.

포텐셜 함수는 $\Phi(D_i) = 2 \times s(D_i) - c(D_i)$으로 정의하겠습니다. $s$와 $c$는 각각 size와 capacity를 의미합니다. 즉, 재할당이 일어난 직후가 가장 이상적인 형태이며, 재할당한 지 오래 지났을수록 자료구조가 망가진 상태로 정의한 것입니다. 동적 배열의 알고리즘을 생각해 보면 항상 $sz \geq cap/2$를 만족하기 때문에 $\Phi(D_i) \geq 0$임을 알 수 있습니다. 따라서 분할 상환 비용의 합은 실제 비용의 합을 나타냅니다.

push_back 연산은 공간의 크기가 확장되지 않는 경우와 확장되는 경우로 나눌 수 있습니다. 두 가지 경우에 대해 각각 분할 상환 비용을 계산해 봅시다.

크기가 확장되지 않는 경우에는 $c(D_i) = c(D_{i-1})$이고, $s(D_i) = s(D_{i-1}) + 1$입니다. 따라서 $\hat{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1})$ $= 1 + (2s(D_{i-1}) + 2 - c(D_{i-1})) - (2s(D_{i-1}) - c(D_{i-1})) = 3$입니다.

크기가 확장되는 경우에는 $c(D_i) = 2c(D_{i-1})$이고, $s(D_i) = s(D_{i-1}) + 1$입니다. 따라서 $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$ $= (1+c(D_{i-1})) + (2s(D_{i-1})+2-2c(D_{i-1})) - (2s(D_{i-1}) - c(D_{i-1})) = 3$입니다. $c_i = 1 + c(D_{i-1})$인 것을 주의해야 합니다.

두 경우 모두 분할 상환 비용이 $O(1)$이므로 연산을 $n$번 수행했을 때의 분할 상환 비용의 총합은 $O(n)$입니다.

4. 동적 배열의 시간 복잡도 분석

4-1. 포텐셜 함수 정의

포텐셜 함수를 다음과 같이 정의합시다. 마찬가지로 재할당이 발생한 직후인 $s(D_i) = c(D_i) / 2$ 일 때가 가장 이상적인 형태이며, 재할당한 지 오래 지났을수록 자료구조가 망가진 상태로 정의했습니다.

\[\Phi(D_i) = \begin{cases} 2s(D_i) - c(D_i) & \text{if } 2s(D_i) \geq c(D_i) & \cdots \enclose{circle}{1} \\ c(D_i)/2 - s(D_i) & \text{if } 2s(D_i) < c(D_i) & \cdots \enclose{circle}{2} \end{cases}\]

빈 배열은 $s(D_i) = c(D_i) = 0$이기 때문에 $\Phi(D_0) = 0$이고, 항상 $\Phi(D_i) \geq 0$을 만족합니다.

4-2. push_back의 분할 상환 비용

push_back 연산으로 인해 ①에 해당하던 자료구조가 ②로 바뀌진 않습니다. 따라서 ① → ①, ② → ①, ② → ② 세 가지만 생각하면 됩니다.

① → ① 은 재할당 여부와 관계없이 분할 상환 비용이 3이라는 것을 위에서 증명했습니다. ② → ②는 재할당이 발생하지 않으므로 간단하게 계산할 수 있습니다. $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$ $= 1 + (c(D_{i-1})/2 - s(D_{i-1})-1) - (c(D_{i-1})/2 - s(D_{i-1})) = 0$입니다. ② → ① 일 때도 재할당은 발생하지 않습니다. 분할 상환 비용의 계산은 다음과 같습니다.

\[\hat{c}_i = c_i + \Phi(D_i) - \Phi(D\_{i-1}) \\= 1 + (2s(D\_{i-1})+2-c(D\_{i-1})) - (c(D\_{i-1})/2 - s(D\_{i-1})) \\= 3 + 3s(D\_{i-1}) - 3c(D\_{i-1})/2\]

이때 $2s(D_{i-1}) < c(D_{i-1})$이므로 $3s(D_{i-1}) - 3c(D_{i-1})/2 < 0$이 돼서 $\hat{c}_i < 3$입니다. 따라서 push_back 연산의 분할 상환 비용은 항상 3 이하입니다.

4-3. pop_back의 분할 상환 비용

pop_back 연산은 ①인 상태에서 재할당이 발생하지 않으며, 이 연산으로 인해 ②에 해당하던 자료구조가 ①로 바뀌진 않습니다. 따라서 ① → ①, ① → ②, ② → ② 세 가지만 생각하면 됩니다.

① → ① 의 분할 상환 비용은 $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$ $= 1 + (2s(D_{i-1})-2 - c(D_{i-1})) - (2s(D_{i-1}) - c(D_{i-1})) = -1$입니다. ① → ② 의 분할 상환 비용은 다음과 같습니다.

\[\hat{c}_i = c_i + \Phi(D_i) - \Phi(D\_{i-1}) \\ = 1 + (c(D\_{i-1})/2 - s(D\_{i-1}) + 1) - (2s(D\_{i-1}) - c(D\_{i-1})) \\ = 2 + 3c(D\_{i-1})/2 - 3s(D\_{i-1})\]

이때 $2s(D_{i-1}) \geq c(D_{i-1})$ 이므로 $3c(D_{i-1})/2 - 3s(D_{i-1}) \leq 0$이 돼서 $\hat{c}_i \leq 2$입니다.

② → ② 는 재할당이 발생하지 않는 경우와 발생하는 경우로 나눠서 계산해야 합니다. 재할당이 발생하지 않으면 $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$ $= 1 + (c(D_{i-1})/2-s(D_{i-1})+1) - (c(D_{i-1})/2-s(D_{i-1})) = 2$입니다. 재할당이 발생하면 $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$ $= (1+c(D_{i-1})/4) + (c(D_{i-1})/4 - s(D_{i-1}) + 1) - (c(D_{i-1})/2 - s(D_{i-1}))$ $= 2$입니다.

따라서 pop_back 연산의 분할 상환 비용은 2 이하입니다.

push_back 연산의 분할 상환 비용과 pop_back 연산의 분할 상환 비용이 모두 $O(1)$이므로 연산을 $n$번했을 때의 분할 상환 비용의 총합은 $O(n)$입니다. 포텐션 함수는 항상 $\Phi(D_i) \geq 0$을 만족하기 때문에 분할 상환 비용의 합은 실제 비용의 합의 상한을 나타냅니다. 따라서 동적 배열의 push_back 연산과 pop_back 연산 모두 amortized $O(1)$ 시간에 동작함을 알 수 있습니다.

더 공부할 거리

과제