Dynamic Array

💡 Dynamic Array는 어떤 자료구조 인가

Array의 경우 size가 고정되었기 때문에 선언시에 설정한 size보다
많은 갯수의 data가 추가되면 저장 할 수 없다
이에 반해 Dynamic Array는 저장공간이 가득 차게 되면
resize를 통하여 유동적으로 size를 조절하여 데이터를 저장하는 구조이다

Dynamic Array의 핵심 요소는 두가지이다

1. resize를 하는 방식
2. 데이터 추가(append)할 때의 시간복잡도

---

resize

해당 A배열에 6이라는 항목을 추가하고 싶다면

B배열을 선언해준뒤 A배열을 복사해주고 6을 추가하면된다

그 후에 A배열은 삭제시켜주면 이것을 우리는 resize라고 한다

---

Doubling

💡 Doubling

resize의 대표적인 방법이다
데이터를 추가(append O(1))하다가 메모리를 초과하게 되면
기존 배열의 size보다 두배 큰 배열을 선언하고 데이터를 일일이 옮기는 방법이다
(N개의 데이터를 일일이 옮겨야 하므로 O(n) 방법이다)

저번 포스팅에 기재한것처럼 array append의 시간 복잡도는 O(1)이다
하지만 doubling이 수행되며 기존 배열의 데이터를 복사하며 O(n)의
시간이 소요되게 된다
이러한 과정에서 Array append의 시간 복잡도는 O(1)일까 O(n)일까 ?

---

분할상환 시간복잡도

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

위 질문에 대한 해답은 여기서 찾아볼 수 있다
append의 총과정을 살펴보면 데이터를 마지막 인덱스에 추가하는(O(1))작업이 대다수이고,
size를 넘어설 때 2배의 size로 늘리고 데이터를 일일이 복사하는 과정(resize O(n))이 아주 가끔 발생함
결론부터 말하자면 append의 전체적인 시간복잡도는 O(1)이다.
정확히 말하자면 amortized O(1) 이라고 부르며
쉽게 설명하자면 가끔 발생하는 O(n)의 resize하는 시간을,
자주 발생하는 O(1)의 작업들이 분담해서 나눠 가짐으로써
전체적으로 O(1)의 시간 복잡도를 갖는다고 생각하면 된다