시간 복잡도는 수행 시간이 아닙니다.

PS/자주 하는 답변

시간 복잡도는 수행 시간이 아닙니다.

djm03178 2023. 1. 28. 12:21

알고리즘의 효율성을 평가하는 기본적인 척도는 시간 복잡도입니다. 문제를 풀 때에도 어떤 알고리즘이 문제의 제한을 시간 내에 통과할 수 있을지 측정하는 용도로 시간 복잡도를 제일 먼저 계산하곤 합니다. 그렇게 해서 나온 시간 복잡도를 가지고 C/C++은 1초에 10억 번 연산을 할 수 있고 PyPy3는 1초에 1억 번을 할 수 있고... 이런 식으로 종종 수행 시간을 예측하고는 합니다. 하지만 이러한 계산 방식에 의존해서는 안 됩니다. 왜냐하면, 시간 복잡도는 수행 시간과는 근본적으로 다르기 때문입니다.

시간 복잡도 vs. 수행 시간

다시 강조하지만 시간 복잡도는 수행 시간과 근본적으로 다릅니다. 복잡도라는 것은 대단히 수학적인 개념으로, 이 글에서 자세히 설명하지는 않겠으나 이해하기 쉽게 말하면 어디까지나 변수들에 대한 어떤 함수에 비례하는지만을 나타낸 것입니다. 그렇기 때문에 시간 복잡도에서 마음껏 추가하거나 생략해도 되는 것들이 있습니다. 바로 상수배와 상수항입니다. 예를 들어서, $\mathcal{O}(N)$, $\mathcal{O}(9999999999999N)$, $\mathcal{O}(\cfrac{N}{9999999999999})$, $\mathcal{O}(N+9999999999999)$, $\mathcal{O}(9999999999999N+9999999999999)$ 등은 모두 같은 복잡도입니다. 이론적으로는 이들 중 어떤 표기를 사용하더라도 모두 $N$에 비례함을 나타내는 문제 없는 표기입니다.

반면에 수행 시간이라는 것은 실제로 프로그램이 해당 코드를 실행하기 위해 걸리는 실질적인 시간입니다. 그런데 이 시간이라는 것은 코드만 보고 정확히 측정하는 것은 매우 어려운 일입니다. 왜 이것이 어려운지를 지금부터 설명하겠습니다.

상수배

위에서는 다소 극단적인 예시를 들었지만 우리가 생각하는 것보다 크고 작은 상수배와 상수항은 어느 코드에나 있습니다. 구체적인 예시들은 이전에 더 빠른 문제 풀이 코드를 위한 상수 줄이기와 더 빠른 문제 풀이 코드를 위한 상수 줄이기 2 글에서 설명한 바가 있으나, 여기서는 간단한 예시만 몇 개 들어보겠습니다.

흔히 버블 정렬과 삽입 정렬의 시간 복잡도는 똑같이 $\mathcal{O}(N^2)$이라고 말합니다. 하지만 이 알고리즘들은 구현하기에 따라서는 최악의 경우에도 루프를 약 $\cfrac{N^2}{2}$번밖에 돌지 않습니다. 삽입 정렬을 예로 들어보면,

	for (int i = 1; i < N; i++)
		for (int j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
			swap(a[j], a[j + 1]);

바깥의 루프는 (대략) $N$번 돌지만, 안쪽의 루프는 많아야 $i$번 돌기 때문에 루프가 도는 횟수를 대략 구해보면,

$$\sum_{i=1}^N{i}\approx\cfrac{N^2}{2}$$

정도가 나옵니다. 그러므로 시간 복잡도를 $\mathcal{O}(N^2)$라고 했음에도 불구하고 실제로 삽입 정렬에 걸리는 시간은 $\cfrac{N^2}{2}$네요... 라고 말하면 안 됩니다! 그 외에도 '상수배'에 영향을 주는 요소는 엄청나게 많기 때문입니다.

루프가 실행될 때 실행하는 문장이 하나가 아닙니다. 루프 한 번을 돌 때마다 swap(a[j], a[j + 1]); 라는 코드를 실행하고 있고, j--라는 증감문도 실행되고, j >= 0 이라는 비교와 a[j] > a[j + 1]이라는 비교, 그리고 이 둘을 && 하는 연산도 수행하고 있습니다.
그렇다면 위에서 언급한 연산이 5개니까 그냥 다섯 배를 하면 되는 걸까요? 그것도 아닙니다. a[j]라는 건 a의 주소에 j만큼의 인덱스를 건너뛰는 위치를 계산한 뒤 메모리로부터 값을 불러오는 복합적인 연산이고, swap이라는 함수를 호출하는 것은 새로운 함수 스택을 만들고 함수의 코드 위치로 점프한 뒤 다시 리턴 주소를 타고 돌아오는 복잡한 과정을 거칩니다.
아, 그러면 이 모든 연산을 전부 최소 단위로 쪼깬 뒤 개수만큼 곱하면 되겠네요? 그것도 아닙니다. 아무리 최소 단위의 연산으로 쪼갠다고 하더라도 각 연산이 소요하는 시간이 모두 같은 것은 아닙니다. 정수간의 덧셈/뺄셈은 곱셈이나 나눗셈보다 빠르고, 주 메모리에서 값을 불러오는 연산은 레지스터 변수를 사용하는 것보다 훨씬 느릴 뿐더러 캐시 히트 등의 외부적인 원인에 의해 완전히 같은 연산임에도 수행 시간에 큰 차이가 발생할 수 있습니다. 게다가 같은 연산을 수행하더라도 컴퓨터의 성능에 따라, CPU의 역량에 따라 수행 속도가 달라집니다. 특정 연산이 다른 연산에 비해 모든 CPU에서 절대적으로 빠르거나 절대적으로 느린 것도 아닙니다.
게다가 컴파일러에게는 최적화라는 흑마법이 있습니다. 예를 들어 위 코드에서 a[j]와 a[j + 1]이라는 요소가 두 번씩 등장하는데, 컴파일러는 그걸 눈치채고 해당 주소를 여러 번 계산하지 않고 빠르게 한 번만 계산하는 식으로 바꾸는 것도 얼마든지 가능합니다. 또한 a[j]의 주소는 본래 a의 위치에 j * sizeof(int)만큼을 더한 위치여야 하지만 느린 곱셈 연산 대신 빠른 시프트 연산 등을 사용하게 할 수도 있고, 느린 연산인 분기를 최소화하기 위해 코드의 실행 순서를 마음대로 바꿀 수도 있습니다.

그 외에도 이 짧은 코드의 실행 시간에 영향을 줄 수 있는 요소는 셀 수 없이 많습니다. 이걸 모두 고려해서 코드만 보고 정확한 시간을 예측하는 것은 거의 불가능에 가까울 뿐만 아니라, '연산의 개수'에 의해 시간이 결정되는 것은 더더욱 아닙니다. 시간 복잡도는 다시 한 번 강조하지만 비례 관계를 나타내는 수학적인 개념이지, 수행 시간을 측정해주는 도구가 아닙니다.

Python에서의 수행 시간

이 개념이 Python과 같은 인터프리터 언어로 넘어가면 계산은 더더욱 복잡해집니다. Python 코드는 직접적으로 기계어로 변환되는 것이 아니라 실행 중에도 인터프리터 레이어를 거쳐가기 때문입니다. CPython의 경우에는 이 인터프리터가 C로 구현되어 있으며 내장 모듈들의 기능들 역시 C 코드로 구현되어 있습니다. 그렇기 때문에 Python에서 '한 문장'의 무게를 논하는 것은 대단히 어려운 일입니다. 단순히 한 문장을 실행하는 데에도 인터프리터의 번역을 거쳐 수많은 C 코드를 지나가야 하기 때문입니다. 어떤 문장이 몇 줄의 C 코드를 실행하게 될지는 예측하기가 매우 어렵습니다.

게다가 Python은 정수 하나도 마음 편하게 사용할 만큼의 속도를 보장해주지 않습니다. 큰 정수 (bigint)를 지원하기 위해 속도를 포기했기 때문입니다. 이는 Python의 큰 정수 표현법 1, Python의 큰 정수 표현법 2 - 사칙연산, Python의 큰 정수 표현법 3 - 기타 연산 등의 글에서 자세히 언급한 바가 있습니다. 쉽게 말해, 하나의 간단한 연산을 수행하더라도 항상 값의 범위 체크 등의 복잡한 과정이 첨가되며, 같은 연산을 수행하더라도 그 시간 차이는 int 변수 하나가 담고 있는 실제 값의 자릿수에 비례, 혹은 그 이상의 차이로 나타나게 된다는 것입니다. 이러한 현상은 int에만 한정된 것만이 아니라 list, dict 등의 다른 내장 자료형들에서도 비슷합니다.

이런 언어에서 '문장의 개수'를 세면서 시간이 얼마 정도 걸릴 거라고 예측하는 것은 크게 의미가 없습니다.

그러면 시간 복잡도는 어떻게 활용해야 하나?

이쯤 되면 시간 복잡도를 계산하는 행위 자체에 회의감을 느끼게 될지도 모릅니다. 그럼에도 불구하고 시간 복잡도는 반드시 계산을 해야 합니다. 아무리 부정확하더라도, 입력의 크기가 충분히 커지면 어쨌든 수행 시간에 가장 크리티컬하게 영향을 줄 요소는 시간 복잡도가 되기 때문입니다. $N \le 10^6$인 문제에서 $\mathcal{O}(N^2)$인 알고리즘 대신 $\mathcal{O}(N\log{N})$인 알고리즘을 생각할 수 있다면 단순히 이 식의 값만으로 이미 수만 배의 이득을 보고 시작하는 것입니다. 위에서 말한 '상수배'에 영향을 주는 요소가 아무리 많다고 하더라도 수만 배의 차이를 극복해내는 것은 웬만해서는 어렵습니다.

시간 복잡도가 우선적으로 계산이 되었다면 그 다음에는 이제 이 '상수배'에 영향을 줄 수 있는 다양한 요소들을 개선하려고 노력해볼 수 있습니다. 입출력을 빠르게 한다거나, 느리다고 알려진 연산들을 피하거나, 캐시 히트가 잘 일어나게 바꾼다거나 하는 것 등이 있을 수 있습니다. 물론 이렇게 한다고 해서 정확히 얼마의 시간이 걸리리라고 예측하기는 어렵지만, 전체적으로 유의미하게 시간이 개선될 것임은 예측할 수 있습니다.

또한 문제들의 제한은 대개는 출제자가 의도한 시간 복잡도의 풀이라면 여유 있게 통과될 수 있는 수준으로 설정되어 있습니다. 이 '여유'는 대개는 다섯 배에서 열 배 이상의 시간입니다. 물론 이보다 빡세게 제한을 설정하는 문제들도 있지만, 기본적인 시간 복잡도만 지킨다면 상수배에 의한 어느 정도의 비효율성은 대부분의 문제에서는 눈감아줍니다.

결론적으로 하고 싶은 말은 문제를 풀 때에는 수행 시간을 예측하기 위해 문장의 개수를 세는 등의 섬세한 계산에 시간을 쏟을 필요가 없다는 것입니다. 시간 복잡도를 기반으로 하여 효율적인 코드를 작성하는 것에 신경쓰는 것이 좋습니다. 어떤 언어가 1초에 몇 개의 문장을 실행할 수 있느니같은 건 아주 대략적으로만 받아들이는 것이 좋고, 그보다는 문제가 어느 정도의 시간 복잡도를 요구하는 것인지를 제한을 통해 추론하고 그 시간 복잡도에 맞는 풀이를 떠올리도록 해야 합니다.