일반적으로 동적배열은 크기를 늘렸다 줄였다 할 수 있다.
줄이는건 메모리가 부족한 환경에서의 관심이고
늘리는게 관건인데, 크기를 하나 데이터를 추가 할때마다 하나씩 늘리면
배열에 요소를 추가하는데 복잡도가 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이 된다.
Researcher & Developer @ NAVER Corp | Designer @ HONGIK Univ.