서론
C++을 사용할 때 거의 필수적으로 사용하는 STL(standard template library)에서 제공해주는 vector class의 method의 시간복잡도를 기억하기 쉽게 이해를 토대로 정리해보자.
필자는 알고리즘을 풀 때 주로 사용한다.
Vector
기본적으로 vector는 자동으로 동적할당 해주는 배열이라고 생각하면 된다.
그러므로 stack이 아닌 heap 메모리를 사용하게 되며, 여러 가지 기능을 제공하는 만큼 단순 배열보다는 속도가 좀 떨어진다.
내부적으로도 ‘배열’의 구조로 데이터를 저장한다. (연속적인 메모리)
또한 vector클래스가 스택에서 해제될 때 자동으로 해당되어 있는 메모리를 전부 해제해줘서 메모리 누수를 고민할 필요가 없다.
시간 복잡도
기본적으로 흔히 사용하는 method에 대해서 알아보자
random access : O(1)
v[4], v.at(4) : 과 같이 임의의 원소에 접근하는 것은 배열과 마찬가지로 시작 주소에서 offset 만큼 연산하여 접근하기에 O(1)이라고 볼 수 있다.
임의의 위치에 원소 추가 및 제거 : O(n)
v.inset(v.begin() + 1, 100);
v.erase(v.begin() + 1);
배열과 마찬가지로 특정 인덱스에 원소를 추가하거나 제거 시 연속적인 메모리를 가져야하기 때문에 그 뒤에 데이터 전부를 한칸씩 옮겨주는 작업이 필요하다. 그래서 O(n) 만큼의 시간복잡도를 가진다.
맨 뒤 위치에 원소 추가 및 제거 : amortized O(1)
v.push_back(100);
v.pop_back();
왜 이건 위와 같이 O(n)이 아니냐.. 또는 배열의 뒤를 늘리면 동적할당을 새로해야하는 것 아니냐.. amortized O(1)은 뭐냐.. 등 의문이 생길 수 있다.
하나씩 설명하자면 vector의 끝에 추가 또는 삭제를 하게 되면 그 뒤에는 아무 원소가 없으므로 한칸씩 옮기는 작업이 필요없다. 또한 vector는 실제로 ptr, size, capacity 의 property를 갖으며 데이터가 4개 밖에 없어도 실제로 사용하는 메모리 양은 4개보다 큰 메모리를 여유있게 할당하여 그 크기를 capacity라고 한다.
그래서 단순히 뒤에 추가하거나 삭제하면 되어서 O(1)인데 만약 여유 있게 할당한 capacity가 꽉 차게 되면 기존 배열을 전부 메모리 해제하고 새로운 메모리를 할당하여 옮기게 된다. 그 때의 메모리 크기는 특정 계산식에 따라서 크기가 할당된다. 자세한것은 직접 찾아보면 좋을 것 같다. 하여튼 이 경우에는 최악의 조건으로 O(n)의 복잡도를 갖게 된다. 하지만 이는 매우 드물게 일어나므로 이 것 때문에 전체적인 시간 복잡도를 O(n)이라고 하기는 무리가 있으니 amortized analysis에 의한 O(1)로 표기를 하게 된다. 이 또한 자세한 것은 직접 찾아보면 좋을 것 같다.
기본적으로 이 정도에 대한 이해가 만족되면 나머지 method에 대해서는 충분히 추측이 가능할 것이다.
이에 대한 인지가 중요한 이유가 자료구조의 특성을 고려하지 않고 코드를 작성하게 되면 매우 비효율적인 프로그램이 될 수 있다. 예를 들어 배열의 앞에 숫자를 계속 추가해야하는 문제인 경우 vector를 사용하면 O(n)을 계속 반복해야 하므로 매우 비효율적이다. 이 경우 큐와 덱과 같은 자료구조를 선정하여 O(1)의 복잡도로 효율적인 프로그램을 작성할 수 있을 것이다.
