[DS] [array] vector DynamicArray ArrayList 등의 동적배열의 시간 복잡도

일반적으로 동적배열은 크기를 늘렸다 줄였다 할 수 있다.

줄이는건 메모리가 부족한 환경에서의 관심이고

늘리는게 관건인데, 크기를 하나 데이터를 추가 할때마다 하나씩 늘리면

배열에 요소를 추가하는데 복잡도가 O(n) 이 걸리게되어 매우 비 효율적이게 된다.

그래서 일반적으로 배열을 재할당할때 2배의 크기로 늘려 재할당을 하게 된다.

그때 시간복잡도는 다음과 같다.

추가(push_back , add , append 등의 함수) -> O(1)

삽입(Insert) -> O(n)

삭제(Erase, Delete) -> O(n)

검색(Search, Find) -> O(n)

삽입 삭제 검색의 복잡도는 계산하기 쉬우니 패스하도록 한다.

벡터의 추가 연산시 데이터를 n개 넣을때, 재할당은 log2(n) 번 일어나게 된다.

(두배씩 늘리니까.. 세배씩 늘리면 log3(n)이 되겠지)

수학적으로 벡터의 추가 시간복잡도를 구하는 공식은 다음과 같다.

재할당시간은 n 이고 나머지는 1의 시간으로 삽입이 이루어지니,

재할당시간을 모두 더한후, 1의 시간을 더하고 n으로나눈 식을 극한으로 보내면 된다.

등비수열의 공식에 의해

r=2, a=1 , N=log2(n) 이다.

위 수식에 대입하면

위와 같은 결과가 나오고 위는 2n-1 이된다.

따라서 분모 수식을 정리하면 2n-1+n-log2(n) 이 되고

3n-log2(n)-1 을 n 으로 나눈 식의 무한대 극한 값은 3이된다.

따라서 벡터 추가연산의 TC는 3이 된다.