Pass by reference와 Pass by value 는 시간복잡도에 영향을 미치는가?

최근 문제를 풀다가 이 참조 녀석때문에 골치를 앓았던 적이 있다.

해법을 찾던 중 reference 와 관련되있을거라 생각했고, 잊고 있던 c++ 강의가 생각났다.

결론적으로 말하면 만약 어떤 함수 안에 $O(T(n))$ 으로 실행되는 값을 넣는 경우, 두가지 방식은 시간복잡도를 바꿀수 있다.

1. pass by reference

bool search(vector<int> &v, int k){
	return binary_search(v.begin(), v.end(), k);
}

다음 코드의 시간복잡도는 $O(\log n)$ 이 된다. 이유는 vector v를 참조로 받았기 때문에 실제로는 참조를 통해서만 binary_search 가 실행되므로 원래 함수의 시간복잡도와 동일하다.

2. pass by value

bool search(vector<int> v, int k){
	return binary_search(v.begin(), v.end(), k);
}

다음은 $O(n)$ 이 되는데 그 이유는 v가 copy되기 때문에 $O(n)$ 이 걸리기 때문이다.

그러므로 함수를작성할 때, 함수를 참조 사용하는 편이 더 좋을 수 있다.

(안그러면 TLE로 계속 고생)