· 개발

배열 끝에 추가하는 append는 왜 O(1)일까: 동적 배열과 상각 시간

가끔 배열 전체를 복사하는데도 append가 O(1)인 이유를 용량과 상각 분석으로 설명하고, Java·C++·Rust·Go 문서가 보장하는 범위와 구현이 정하는 증가율, 용량을 미리 잡는 방법을 정리했습니다.

개발알고리즘자료구조

Python의 list.append, Java의 ArrayList.add, C++의 vector::push_back, Rust의 Vec::push는 보통 “끝에 하나 추가하는 데 O(1)“이라고 소개됩니다. 그런데 이 자료구조들은 원소를 연속된 배열 하나에 담아 두고, 배열이 가득 차면 더 큰 저장 공간을 확보합니다. 이 과정에서 새 배열을 할당해 저장된 값을 모두 옮길 수 있습니다. Python과 Java의 배열에는 객체 자체가 아니라 객체를 가리키는 참조가 들어 있으니, 이때 옮겨지는 것은 참조입니다. 가끔 n개를 옮기는데도 O(1)이라고 부를 수 있는 건 이 O(1)이 상각(amortized) O(1)이기 때문입니다.

크기와 용량

동적 배열은 숫자 두 개를 따로 관리합니다. 지금 들어 있는 원소 수(크기)와, 다시 할당하지 않고 담을 수 있는 칸 수(용량)입니다. Java ArrayList 문서는 용량을 원소를 저장하는 배열의 크기라고 설명하고, 용량은 항상 리스트 크기 이상이라고 적습니다.

크기가 용량보다 작으면 추가는 빈칸 하나에 값을 쓰면 끝납니다. 크기가 용량과 같으면 저장 공간을 늘려야 하며, 새 배열을 할당해 값을 옮길 수 있습니다. Rust Vec::push 문서는 재할당이 필요한 경우 용량에 비례하는 O(capacity) 시간이 든다고 적어 두었습니다.

상각 O(1)의 계산

빈 배열에서 시작해 용량을 매번 두 배로 늘린다고 해 봅시다. 원소가 1, 2, 4, 8…개로 찰 때마다 복사가 일어나므로, n번 추가하는 동안 옮기는 원소 수는 1 + 2 + 4 + …이고 이 합은 2n보다 작습니다. 총비용이 n에 비례하니 한 번에 드는 비용은 평균 상수입니다. 이 평균은 입력이 무작위라는 가정에서 나온 값이 아닙니다. 빈 배열에서 시작한 n번의 추가는 무엇을 넣든 총비용이 n에 비례한다는 뜻입니다. 이미 용량이 꽉 찬 큰 배열에서 세기 시작하면 첫 추가 한 번에 큰 비용이 들 수 있으므로, 이 계산은 빈 배열에서 시작하는 경우를 기준으로 합니다.

늘리는 방식이 중요합니다. 새 용량을 max(1, ceil(r × 기존 용량))처럼 정해 반드시 증가시키는 규칙에서, r이 1보다 큰 고정값이면 복사량은 등비수열의 합이라 n에 비례합니다. 예를 들어 r을 1.5로 둘 수 있습니다. 반대로 매번 10칸씩 더하면 복사량이 n²에 비례합니다. 아래 코드로 빈 배열에 원소 100만 개를 추가하는 경우를 세어 보면, 두 배 증가는 복사 1,048,575번(첫 할당을 포함한 할당·증가 21번), 10칸씩 증가는 49,999,500,000번(할당·증가 10만 번)입니다.

def count_copies(n, grow):
    cap = size = copies = 0
    for _ in range(n):
        if size == cap:
            copies += size
            cap = grow(cap)
        size += 1
    return copies

count_copies(10**6, lambda c: max(1, c * 2))  # 1048575
count_copies(10**6, lambda c: c + 10)         # 49999500000

문서가 보장하는 것과 구현이 정하는 것

공식 문서와 명세는 대체로 결과만 약속하고 증가율은 정하지 않습니다.

  • Java ArrayList: 원소 추가가 상각 상수 시간 비용을 가진다는 것 외에는 증가 정책을 정하지 않는다고 적습니다.
  • C++ 표준 공개 작업 초안: vector의 push_back 같은 연산은 상각 상수 시간이 걸리도록 구현한다고 요구합니다. 배율은 없습니다.
  • Rust Vec: 특정 증가 전략을 보장하지 않지만, 어떤 전략을 쓰든 push의 상각 O(1)은 보장한다고 적습니다.
  • Go 명세: 용량이 부족하면 append가 충분히 큰 새 배열을 할당한다고만 말합니다.

실제 배율은 구현이 정합니다. CPython 3.13의 list_resize는 원소를 하나씩 추가할 때 새 크기에 그 1/8과 6을 더한 뒤 4의 배수로 맞춥니다. 소스 주석에는 0, 4, 8, 16, 24, 32, 40, 52, 64, 76…이라는 증가 패턴이 적혀 있습니다. 다만 extend처럼 한 번에 많이 늘려서 새 크기와 이전 크기의 차이가 계산된 할당 용량과 새 크기의 차이보다 크면, 여분 없이 새 크기를 4의 배수로 올린 만큼만 잡습니다. 기본 GIL 빌드에서는 realloc으로 크기를 바꾸므로, 할당기가 제자리에서 늘려 주면 복사 없이 끝나기도 합니다. free-threaded 빌드는 새 배열을 할당하고 복사합니다. OpenJDK 21의 ArrayList는 기존 용량의 절반을 선호 증가량으로 넘기므로, 하나씩 추가할 때 보통 크기에서는 용량이 약 1.5배가 됩니다. 둘 다 버전에 따라 바뀔 수 있는 내부 구현이니 코드가 이 숫자에 기대면 안 됩니다.

상각 O(1)의 한계

상각 O(1)은 호출 하나하나가 빠르다는 보장이 아닙니다. 저장 공간을 늘리는 과정에서 새 배열을 할당해 값을 옮기면 최악에는 원소 수에 비례하는 시간이 걸리므로, 응답 시간의 최댓값이 중요한 코드에서는 가끔 튀는 구간이 생길 수 있습니다.

새 배열을 할당하는 성장은 원소의 위치도 바꿉니다. C++ 표준 초안은 재할당이 원소를 가리키는 참조, 포인터, 반복자를 모두 무효화한다고 적습니다. Go에서는 용량이 충분하면 append가 기존 배열을 다시 쓰고 부족하면 새 배열을 할당하므로, 반환된 슬라이스를 받아서 써야 합니다.

개수를 미리 알 때

넣을 원소 수를 대략 안다면 용량을 먼저 잡아 재할당 횟수를 줄일 수 있습니다. C++의 reserve, Java의 ensureCapacity, Rust의 with_capacity와 reserve가 그 역할을 합니다. 보장의 강도는 다릅니다. C++ 표준 초안은 reserve 이후 크기가 용량을 넘기 전까지 삽입 중 재할당이 없다고 적는 반면, Java 문서는 ensureCapacity가 재할당을 줄일 수 있다고만 말합니다.

정렬 쪽 이야기가 궁금하다면 안정 정렬 글도 함께 읽어 보세요.

참고한 명세와 문서

블로그로