데이터 구조에서 배열 배가(Array Doubling)의 이해와 시간 복잡도 분석

배열 배가란 무엇인가?

프로그래밍에서 배열은 종종 동적 메모리 할당(dynamic memory allocation) 방식으로 생성됩니다. 동적 할당으로 만들어진 배열이라면 몇 가지 연산을 통해 배열의 크기를 두 배로 늘릴 수 있는데, 이러한 기법을 배열 배가(Array Doubling)라고 합니다. 이 기법은 C++의 vector, Java의 ArrayList처럼 크기가 유동적으로 변하는 동적 배열(Dynamic Array)을 구현할 때 핵심적인 원리로 사용됩니다.

배열 배가의 예시

초기 배열의 크기가 5라고 가정해 보겠습니다.

배열 배가 전 (크기 5)

배열 배가를 수행하면 배열의 크기는 다음과 같이 늘어납니다.

배열 배가 후 (크기 10)

배열 배가의 수행 과정

크기가 n인 배열 arr(arr[0…n-1])의 크기를 두 배로 늘리려면 다음 세 단계를 거쳐야 합니다.

1. 새 배열 생성: 크기가 m인 새로운 배열을 하나 생성합니다.
2. 요소 복사: 기존 배열 arr에 있던 n개의 요소를 새 배열로 모두 복사합니다.
3. 참조 변경: arr이 더 이상 기존 배열이 아닌 새 배열을 가리키도록 참조 값을 변경합니다.

시간 복잡도 분석

크기가 m인 배열을 생성하는 데는 θ(m)의 시간이 소요됩니다. 이는 새 배열이 생성될 때 기본값(default value)으로 초기화되기 때문입니다. 이후 기존 배열에서 새 배열로 n개의 요소를 복사하는 데는 추가로 θ(n)의 시간이 필요합니다. 따라서 전체 연산에는 θ(m + n)의 시간이 걸립니다.

중요한 점은 이 연산이 배열이 가득 찬 경우에만 발생한다는 것입니다. 그리고 일반적으로 m의 값은 2n과 같으므로, 복잡도는 다음과 같이 계산됩니다.

θ(2n + n) = θ(3n) ≡ θ(n)

분할 상환 분석(Amortized Analysis)

θ(n)의 비용은 한 번의 연산으로 보면 상당히 비싸게 느껴질 수 있습니다. 하지만 이 비용은 이후 이어지는 n번의 삽입 연산에 걸쳐 분할 상환(amortized)되기 때문에, 실제로는 반복당 θ(1), 즉 상수 시간만 추가될 뿐입니다.

결론적으로, 배열의 크기를 상수 인수(constant factor)만큼 증가시키는 것은 점근적 복잡도(asymptotic complexity)에 악영향을 주지 않습니다. 바로 이러한 이유 때문에 대부분의 동적 배열 구현체들이 공간이 부족해질 때마다 배열 크기를 두 배씩 늘리는 전략을 채택하고 있는 것입니다.