[C++로 배우는 알고리즘과 자료구조 심화] Day 23: 분할 상환 분석 (Amortized Analysis)

분할 상환 분석 (Amortized Analysis)

분할 상환 분석은 알고리즘의 시간 복잡도를 분석하는 기법으로, 개별 연산의 최악의 경우 시간 복잡도가 아닌, 일련의 연산에 대한 평균 시간 복잡도를 계산하는 방법입니다. 이는 데이터 구조의 연산이 불균등하게 발생할 때 매우 유용합니다. 분할 상환 분석의 주요 기법에는 Aggregate Analysis, Accounting Method, Potential Method가 있습니다.

Aggregate Analysis

Aggregate Analysis는 전체 연산에 대해 총 비용을 계산하고, 이를 연산 수로 나누어 평균 비용을 구하는 방법입니다.

Accounting Method

Accounting Method는 각 연산에 대해 가상의 "크레딧"을 할당하여 연산 비용을 분할하는 방법입니다. 이 크레딧은 실제 연산 비용보다 많거나 적을 수 있으며, 나중에 사용할 수 있습니다.

Potential Method

Potential Method는 시스템의 상태에 따른 "잠재적 에너지"를 정의하여, 각 연산에 대해 잠재적 에너지의 변화와 실제 연산 비용을 합산하여 계산하는 방법입니다.

문제 예시: 동적 배열

동적 배열의 크기를 동적으로 조정하는 문제에서, 크기를 두 배로 늘리거나 반으로 줄일 때 분할 상환 분석을 사용할 수 있습니다.

문제 정의

동적 배열을 사용하여 요소를 추가하고 삭제하는 연산이 주어졌을 때, 각 연산의 평균 시간 복잡도를 계산합니다.

분할 상환 분석 구현

다음은 C++로 동적 배열의 크기 조정을 분할 상환 분석으로 해결하는 예제입니다.

#include <iostream>
#include <vector>

class DynamicArray {
public:
    DynamicArray() : capacity(1), size(0) {
        arr = new int[capacity];
    }

    ~DynamicArray() {
        delete[] arr;
    }

    void push_back(int value) {
        if (size == capacity) {
            resize(2 * capacity);
        }
        arr[size++] = value;
    }

    void pop_back() {
        if (size > 0) {
            size--;
            if (size > 0 && size == capacity / 4) {
                resize(capacity / 2);
            }
        }
    }

    int get(int index) const {
        if (index >= 0 && index < size) {
            return arr[index];
        }
        throw std::out_of_range("Index out of range");
    }

    int getSize() const {
        return size;
    }

private:
    void resize(int newCapacity) {
        int* newArr = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            newArr[i] = arr[i];
        }
        delete[] arr;
        arr = newArr;
        capacity = newCapacity;
    }

    int* arr;
    int capacity;
    int size;
};

int main() {
    DynamicArray dynArr;

    for (int i = 0; i < 10; i++) {
        dynArr.push_back(i);
        std::cout << "Added " << i << ", size: " << dynArr.getSize() << std::endl;
    }

    for (int i = 0; i < 8; i++) {
        dynArr.pop_back();
        std::cout << "Removed element, size: " << dynArr.getSize() << std::endl;
    }

    return 0;
}

 

설명

1. push_back 연산:
   • 동적 배열의 크기가 현재 용량에 도달하면, 배열 크기를 두 배로 늘립니다.
   • 이는 (O(n))의 최악의 경우 시간 복잡도를 가집니다. 그러나 분할 상환 분석을 통해 연산의 평균 시간 복잡도를 계산할 수 있습니다.
   • 평균 시간 복잡도는 (O(1))입니다.
2. pop_back 연산:
   • 동적 배열의 크기가 현재 용량의 1/4이 되면, 배열 크기를 반으로 줄입니다.
   • 이는 (O(n))의 최악의 경우 시간 복잡도를 가집니다. 그러나 분할 상환 분석을 통해 연산의 평균 시간 복잡도를 계산할 수 있습니다.
   • 평균 시간 복잡도는 (O(1))입니다.

 

동적 배열의 크기 조정 문제에서 분할 상환 분석의 기본 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 24: 확률적 알고리즘(Monte Carlo, Las Vegas 알고리즘)"에 대해 학습하겠습니다.