[알고리즘] C++에서의 STL과 함수인자

본 글은 바킹독님의 '실전 알고리즘' 강의로부터 필기한 내용입니다.

STL을 함수 인자로 넘길 때

STL은 C++에서 제공되는 라이브러리(Standard Template Library)로, 여기선 배열과 비슷한 기능을 수행하는 vector STL만 소개하겠다.

bool cmp(vector<int> v1, veector<int>v2, int idx){
	return v1[idx] > v2[idx] ;
}

다음 두 vector를 인자로 넘겨받아 idx번째 원소 값을 비교한 결과를 반환한 함수이다. 이 함수의 시간복잡도는 v1,v2의 크기가 N이라고 할 때 몇일까?
O(1)일까? 아니다. O(N)이다!

왜?

STL을 쌩으로 함수 인자에 넣으면 STL이 복사해서 들어간다.
v1,v2를 인자로 실어서 보낼 때 원본으로부터 복사본을 만드는 비용 때문에 O(N)이 나오는 것. (N개의 원소들을 하나하나 복사하는 과정)

참조자(&)를 이용하면 이를 해결할 수 있다.

bool cmp1(vector<int> v1, vector<int> v2, int idx){
	return v1[idx]> v2[idx];
}

cmp1은 벡터를 통째로 복사해버리지만

bool cmp2(vector<int>& v1, vector<int>& v2, int idx){
	return v1[idx]> v2[idx];
}

cmp2는 v1,v2의 type을 vector의 reference로 만들었기 때문에, cmp2가 호출될 때 복사본을 따로 만들어내지 않고 참조 대상의 주소 정보만 넘어가게 된다.
즉 cmp2에서는 O(1)이 된다.