동적 배열(Dynamic array)

동적 배열 : 자료의 개수가 변함에 따라 크기가 변경되는 배열

-메모리 상의 연속적인 공간을 할당

-동적배열은 동적으로 할당받은 배열(new를 통한)을 사용

 

 

동적배열은 배열에 비해 다음과 같은 특성을 지님

-resize() 연산 가능 - 배열의 크기를 변경하는 //  배열의 크기 N에 비례하는 시간 걸림

-append()연산 - 주어진 원소의 배열의 맨끝에 원소 추가하는 

 

동적배열의 메모리 할당방법

-capacity메모리 정책 사용

-메모리를 할당받을 때 배열의 크기가 커질 때를 대비해서 여유분의 메모리(capacity)를 미리 할당받음

-size가 capacity를 넘어서는 경우, 기존메모리 size의 반만큼 늘리고 (결과값이 소수점이면 내림) 배열의 원소를 그쪽으로 옮김

int size; //배열의 크기
ElementType* array; //실제 배열을 가리키는 포인터

동적배열의 append() 연산 시간 복잡도

-size < capacity 경우 O(1) 걸리다가, 

 size  = capacity 경우 재할당 연산을 수행해야 돼서 O(N+M)이 걸림 // N : 원래 원소갯수 , M : 추가 여유 공간 크기

 

-이를해결하기 위해서 재할당을 할때 마다 정해진 크기(상수)를 확보하는 것이 아니라, 현재 가진 원소의 개수에 비례해서 여유크기를 확보

-이런 식이면, 평균적으로 O(1)이 걸림

 

*제일 좋은 방법은 배열의 최종 크기를 미리 안다면, 동적 배열의 용량을 사전에 충분히 늘려둬서 재할당에 드는 비용을 없앰 ( C++의 reserver()이용해서)