동적 배열(Dynamic Array)?

동적배열이란?

대표적인 동적배열은 C++의 Vector와 같은 형태가 있다.

일반적인 배열(Array)은 기본적으로 Fixed-size이기 때문에 선언시 설정한 size보다 많은 갯수의 data가 추가되면 저장할 수 있는 공간이 없는 문제가 발생한다! 하지만 Dynamic Array같은 경우 저장공간이 가득 찰경우 저장공간을 resize하여 유동적으로 조절하여 데이터를 저장하는 자료구조이다.

resize의 과정?

resizing의 대표적 방법은 기본 Array size의 2배를 할당하는 Doubling방식이 있다. Dynamic Array같은 경우 data를 추가하다 기존 할당된 Memory를 초과하게 되면 size를 늘린 새로운 배열을 선언하고 그곳으로 모든 데이터를 옮김으로써 늘어난 크기의 size를 가진 배열이 된다.

분할 상환 시간복잡도(Amoryized time complexity)

Dynamic Array에 데이터를 추가할때마다 O(1)의 시간이 걸리고 메모리를 초과할 경우 resize된 배열로 data를 옮겨야 하기때문에 O(N)의 시간복잡도를 가진다.

결과적으로 O(1)의 복잡도인가 O(N)의 복잡도인가?

답은  O(1)로 대다수의 작업에서는 append O(1)의 시간을 사용하고 size를 넘어서는 경우에만 resize O(N)의 시간이 발생하는데 결론적으로 전체적인 시간복잡도를 볼땐 amortized O(1)을 가진다.

• #amortized 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 시간 복잡도를계산

쉽게 말해 가끔 발생하는 O(N)의 시간을들을 O(1)의 작업들이 분담하여 나눠 가짐으로써 전체적인 시간은 O(1)이 되는 것이다.

 

2024.02.22 - [study/CS] - 배열(Array)?