[CS/자료구조] Dynamic Array란?

1. 동적 배열(Dynamic Array)

크기가 고정되어 있어 할당한 크기보다 많은 갯수의 데이터를 저장할 수 없는 배열과는 달리 유동적으로 저장공간을 resize할 수 있는 자료구조.

특징

• 데이터 추가 시 기존에 할당된 크기를 초과하게 되면 사이즈를 늘린 배열을 선언하고 그곳으로 기존의 데이터를 옮기는 resizing이 일어난다.

Doubling

• 대표적인 resizing 방법으로 데이터 크기가 초과하게 되면 기존의 크기의 두배에 해당되는 배열을 선언하고 기존 데이터를 옮기는 방법이다. 데이터를 일일이 옮겨줘야 하기 때문에 O(n)의 시간 복잡도를 가진다.

데이터 삽입 시의 시간 복잡도 - Amortized O(1)

데이터를 삽입할 때 동적 배열에서는 할당된 크기 내에서는 O(1)만큼의 시간 복잡도를 갖다가 고정 크기보다 커지게 되면 데이터를 새로운 배열에 옮겨주는 시간이 추가되어 O(n)의 시간 복잡도를 갖는다. 일반적으로는 resizing이 일어나는 경우보다 기존 배열에 데이터를 추가하는 상황이 더 빈번하게 일어나게 된다. 그렇다면 동적 배열의 시간 복잡도는 O(1)일까, O(n)일까?

이러한 경우 시간 복잡도는 분할상환 분석(Amortized Analysis)으로 표현할 수 있다.

동적 배열에서 더블링이 발생하는 경우는 어쩌다 한번이므로 더블링 시 발생하는 O(n)의 시간을 자주 발생하는 O(1)의 작업들에게 나눠주는 형태로 시간 복잡도를 계산하는 것이다. 이렇게 되면 전체적으로 동적배열은 Amortized O(1)의 시간 복잡도를 갖는다고 할 수 있다.

// cpython/Objects/listobject.c
// The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)

위 코드는 파이썬의 리스트를 구현한 CPython 코드인데, 파이썬의 그로스 팩터를 보면 초반에는 2였다가 전체적으로는 1.125정도로 구현되어 있음을 알 수 있다.

참고
[알고리즘] 분할 상환 분석(Amortized Analysis)
개발남노씨