2. 벡터 vector 의 기본 (Time Complexity 시간 복잡도)_C++

연속적인 메모리 공간을 heap에 가질 수 있는 벡터 컨테이너에 대해 조금 더 알아보자.

Cppreference에서 vector를 검색해보면 time complexity에 대한 내용이 나온다.
https://en.cppreference.com/w/cpp/container/vector

std::vector - cppreference.com

The complexity (efficiency) of common operations on vectors is as follows:

• Random access - constant O(1)
• Insertion or removal of elements at the end - amortized constant O(1)
• Insertion or removal of elements - linear in the distance to the end of the vector O(n)

간략히 말하면 random access 랜덤한 접근은 time complexity가 O(1),
벡터의 마지막 파트에 element 요소를 빼거나 넣는 동작은 O(1),
일반적인 삽입과 제거는 O(n) 이라고 쓰여 있는 것이다.

Time Complexity는 번역하면 시간 복잡도 라고 번역할 수 있고, 자세한 내용은 구글링하면 잘 나온다!
요약하면 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계가 된다.

벡터의 random access의 Time Comlexity

int 자료형의 nums 라는 벡터를 만들고 1이라는 숫자 10000개를 넣어보자.

#include <vector>

int main()
{
	std::vector<int> nums(10000, 1);

	return 0;
}

이 상태를 그림으로 나타내 보면, 
위쪽 스택 위에 nums 벡터 오브젝트가 만들어지고 아래쪽 힙 공간 안에 10000개의 array가 만들어 졌으며, 이 array 안에는 전부 1이 들어있는 상태이다. 
그리고 당연히 벡터 오브젝트 nums는 힙 위 array를 가리키고 있다.

위에서 확인했듯 cppreference 는 vector의 random access 는 O(1)의 시간 복잡도를 갖는다고 나와 있다.
즉 1만개의 element요소가 들어있는 벡터가 힙 공간에 있는데, 
첫 번째 공간에 접근할 때
마지막 공간에 접근할 때,
그리고 중간에 있는 어떠한 공간에 접근할 때 시간이 O(1) 으로 같다는 의미이다. 
(캐시와 같은 하드웨어 제약을 제외하고 말하는 것)

벡터의 Random Access의 Time Complexity O(1)

이 벡터의 random access가 어떻게 O(1)의 시간 복잡도를 갖게 되는가?
벡터는 이 연속된 배열의 가장 첫 번째 공간을 가리키고 있다.
그리고 벡터는 항상 연속적으로 모든 데이터(요소)가 놓여져 있다는 것이 보장되어 있기 때문에
시작점만 알고 그로부터 몇 번째 요소에 접근하고 싶은지 알게 되면 바로 접근이 가능하다.

예를 들어 위와 같이 가장 첫 번째 요소의 주소가 1000이라고 가정했을 때, 2005번째 공간에 접근하고 싶다면 
주소 1000 + 2005 = 3005, 즉 주소 3005에 다이렉트로 접근이 가능하다는 것이다.

결국 컴퓨터는, 시작점을 알고 몇 번째 떨어져 있는 곳에 원하는 데이터가 있는지 알기 때문에
벡터의 길이와 상관없이 또는 접근하고자 하는 위치와 상관없이 늘 constant 정해진 시간에 접근이 가능하기 때문에
모두 O(1)의 시간 복잡도를 갖는다고 할 수 있는 것이다.

벡터의 끝 부분에 요소를 삽입하거나 제거하는 경우의 Time Complexity

 다음으로 cppreference에서 언급된 내용은,

• Insertion or removal of elements at the end - amortized constant O(1)

 벡터의 마지막 공간에 삽입하거나 제거하는 행위는 O(1)의 시간 복잡도를 갖는다는 것이다.
앞선 게시글에서 언급했듯 함수인 emplace_back()을 통해 마지막에 요소를넣어준다거나,
pop_back()을 통해 마지막 요소를 제거할 수 있었다.

#include <vector>

int main()
{
	std::vector<int> nums(10000, 1);

	nums.emplace_back(2);
	nums.pop_back();

	return 0;

 앞서 언급했듯 벡터nums는 배열의 가장 첫 번째 공간을 가리키고,
벡터는 10000개의 element 요소를 가지고 있다는 것을 이미 알고 있기 때문에
10001번째 공간까지 간 후에 공간을 만들어 주고 emplace_back(2)로 2를 넣어주게 되면 
정해진 시간 안에 데이터를 추가로 넣어주었기 때문에 O(1)의 시간 복잡도를 갖는다고 할 수 있는 것이다.

pop_back(); 경우에도 시작점에서 10001번째 떨어진 곳에서 숫자 2를 제거만 해 주면 되기 떄문에 
벡터의 길이나 요소의 위치와 상관없이 늘 정해진 시간 내에 삭제가 가능하다.
즉 O(1)의 시간 복잡도를 갖는다는 것이다.

벡터 끝 부분 삽입 제거의 TimeComplexity는 O(1)

 

벡터의 끝 부분이 아닌 공간에 요소를 넣고 뺄 때의 Time Complexity

• Insertion or removal of elements - linear in the distance to the end of the vector O(n)

마지막으로 마지막 공간이 아닌 다른 공간에 요소를 넣고 뺄 때는 O(n)의 시간 복잡도를 갖는다고 한다.

#include <vector>

int main()
{
	std::vector<int> nums(10000, 1);

	nums.emplace(nums.begin(), 3);
	nums.erase(nums.begin());

	return 0;
}

nums.emplace(nums.begin(),3); 함수를 통해 시작점에 3을 넣어줄 수 있다.
nums.erase(); 함수를 통해 첫 번째 위치를 지워줄 수 있다.

 첫 번째 명령어를 보면
벡터 array 공간에 10000개의 1이 전부 들어 있는데 가장 첫 번째 공간에 3을 넣어주려고 하고 있다.
벡터의 사이즌ㄴ 10000개에서 10001개가 되어야 하고 
모든 요소가 옆으로 한 칸씩  move를 해야 하는 상황인 것이다.
즉 3이라는 숫자를 맨 앞에 넣어주기 위해서 총 10000번의 move가 일어나게 되고
결국 O(n)의 시간 복잡도를 갖게 되는 것이다.

힙 위에 배열 공간에 3을 맨 앞에 넣어주기 위해서 10000번의 move가 일어나게 된다.

 다음으로 nums.erase(); 를 통해 가장 첫 번째 element를 삭제해 주었다.
이 때도 마찬가지로 모든 element를 앞쪽으로 1칸씩 move 해 주어야 하고 
총 10000번의 move가 일어나게 되고 마지막 공간에 아무것도 남지 않으면서 삭제해 주어야 한다.
총 O(n)의 time complexity를 가지고 element를 지워주는 것이다.

Time Complexity 시간 복잡도에 따른 벡터 사용 권장사항

  벡터를 사용할 때는,
O(1)의 시간 복잡도를 갖는 random access와 
마찬가지로 시간 복잡도가 O(1)마지막 공간에 데이터를 넣거나 빼는 emplace_back(); pop_back(); 같은 명령어를 사용해야 한다. 만약 마음대로 벡터 중간에 요소를 넣거나 빼게 되면 O(n)의 time complexity를 갖게 된다.
결국 O(n)의 시간 복잡도를 갖는 벡터 중간에 넣거나 빼는 행위는 다시 한번 생각해보고 
이런 동작이 정말로 필요한지 다시 한번 생각해보아야 한다!
즉 웬만한 경우가 아니면 시간 복잡도 때문에 이런 벡터 중간에 요소를 삽입/제거 insertion/removal 행위는하지 않는 것이 좋다는 것이다!    

다음 이어지는 내용
emplace_back() 에 대한 심화