3. 시간복잡도, 공간복잡도, big-O notation

앞 글들에서 효율적인 알고리즘의 중요성과 효율적인 알고리즘을 만드는 하나의 방법에 대해 알아보았다. 이쯤에서, 효율적인 알고리즘이란 무엇인가? 라는 고민을 해 볼 필요가 있을 것이다. 가장 근본적인 대답은, 프로그램의 실행 시간과 메모리가 적은 알고리즘이 효율적인 알고리즘이라는 것이다. 그렇다면 무엇이 실행 시간과 메모리를 결정하는가? 간단히 말하면 다음과 같다.

• 실행 시간 : 프로그램이 실행되는 동안의 총 연산 횟수에 비례한다. 다양한 연산자의 작동(+, -, &, ||, ...), 값의 대입과 변경 등 기본적인 실행이 총 몇 번 일어나는지 생각해보면 된다. 물론 연산의 종류에 따라(비트 연산은 보통 다른 연산들보다 빨라 정수를 2로 나눈 몫을 계산할 때 /2보다 >>1을 선호하기도 한다), 또 기술적인 상황에 따라(캐시히트 등) 실행 시간이 달라지므로 완벽히 비례한다고는 볼 수 없지만 PS의 영역에서는 대충 연산의 횟수만 세어줘도 된다. 물론 백준에서 푼 사람이 많은 문제의 실행 시간 1등 코드를 눌러보면 종종 이러한 기술적인 요인까지 고려해가며 극한으로 실행 시간을 줄인 코드가 나오기도 한다. 자세한 것은 뒤에서 설명한다.
• 메모리 : 비교적 계산하기 편하다. 선언하는 총 변수의 양에 비례한다고 생각하면 된다. 보통 프로그래밍을 처음 시작할 때 배웠을 'int형은 4바이트, long은 8바이트, ...'를 떠올리면 편하다. 종종 메모리를 최대한 효율적으로 사용하는 것이 의도인 문제가 존재하는데, 그러한 경우를 제외하면 실행 시간이 제한 내에 들어오는데도 메모리가 제한을 넘는 경우는 PS에서 매우 드물다.

 
그러나 위 설명은 어딘가 답답한 면이 있다. 코드를 짤 때마다 "$n$이 100일 때 내 코드는 덧셈을 213324번, 뺄셈을 128821번, ..." 하면서 연산 횟수를 모두 세는 것은 현실적으로 불가능할 뿐더러, 그렇게 세어봤자 정확한 실행 시간을 유추할 수도 없기 때문이다. 메모리 역시 마찬가지이다. 따라서 아주 큰 수를 어림하는 새로운 방법을 필요로 하게 된다.

---

코드는 대부분 입력에 따라 연산 횟수가 달라진다. 즉 연산 횟수가 입력에 따른 함수라고 생각할 수 있다. $n$을 입력으로 받는 어떤 코드의 연산 횟수가 $f(n)$이라고 하자. 다음 중 어떤 코드가 가장 효율적이라고 생각하는가?
 
1. $f(n) = 5000$
2. $f(n) = 100n+100$
3. $f(n) = n^2 +\sqrt{n}$
4. $f(n) = \log_{2} {n}$
 
$1 \leq n \leq 10$ 정도일 때는 1, 3, 2, 4 순서대로 $f(n)$의 값이 작을 것이다. 그러나 $n$이 커짐에 따라 어느 순간부터 1, 4, 2, 3의 순서대로 $f(n)$의 값이 작게 됨을 알 수 있다. 보통 PS에서 다루게 되는 문제들은 $n$의 제한을 충분히 크게 주는 경우가 많기 때문에, 우리는 위와 같은 상황에서 1, 4, 2, 3의 순서로 효율적이라고 보는 시각을 갖출 필요가 있다.
 
이를 엄밀하게 정의하고, 또 간편하게 소통할 수 있게 하는 도구가 바로 big-O notation이다. big-O notation의 수학적으로 엄밀한 정의는 나무위키에 친절하게 설명되어 있으니, 여기서는 간단히 어떤 표기법인지만 설명하겠다. 예시를 통해 알아보자.
 
1. $f(n) = 5000 = O(1)$
2. $f(n) = 100n+100 = O(n)$
3. $f(n) = n^2 + \sqrt{n} = O(n^{2})$
4. $f(n)= \log_{2} {n} = O( \log {n})$
 
즉 $f(n)$의 가장 큰 항만 남기고 계수를 뗀 후 $O$ 안에 넣는다고 생각하면 편하다. 위 나무위키를 읽고 왔다면(그렇지 않다면 이 문장은 넘겨도 좋다.) $100n+100 = O(n^3)$으로 표기해도 문제는 없다는 사실을 알겠지만, 그렇게 하면 실행 시간을 big-O notation으로 표기하는 의미를 잃게 되므로 보통 가장 타이트한 표기를 택한다.
 
이렇게 입력값에 따라 프로그램의 실행 시간이 어떻게 변하는지에 대한 추세를 나타내는 값을 시간복잡도라고 한다. 앞으로 '따라서 이 풀이의 시간복잡도는 $O(n\log{n})$이다'라고 한다면, $n$이 매우 커질 때 코드의 실행 시간이 $n\log{n}$ 정도의 스케일로 증가함을 의미한다. PS란 무엇인가?에서 한 번 언급했지만, PS를 할 때 컴퓨터는 1초에 수억 번의 연산이 가능하다고 생각하는 것이 좋다. 따라서 1초의 시간 제한이 있는 문제에서 $n \leq 100$이라면 시간복잡도는 $O(n^{4})$, $n \leq 100000$이라면 시간복잡도는 $O(n\log{n})$ 혹은 $O(n\log^{2}{n})$ 정도가 최대라고 볼 수 있다. 즉 PS를 할 때는 보통 $O$ 안에 들어가는 함수에 제한 내의 최악의 케이스를 넣었을 때 1억 근방이 되는 시간복잡도까지를 갖는 알고리즘을 만들게 된다.
 
물론 과거 codeforces에서 $n \leq 100$인데 정해가 $O(n^{5})$인 문제가 출제된 적도 있다. 이렇듯 시간복잡도는 보통 코드의 실행 시간에 대한 적절한 어림값을 제공해주지만, 상수 차이라고 부르는, big-O notation으로 봤을 때는 차이가 없는 요인으로 인해 제한을 통과하지 못할 것 같은 시간복잡도의 코드가 제한을 통과하는 경우도 있으니 big-O notation으로 나타낸 시간복잡도가 만능은 아니라는 것을 알아두어야 한다.
 
공간복잡도 역시 big-O notation으로 나타낼 수 있다. 시간복잡도의 표기와 크게 다를 것이 없고, 위에서 언급했듯 많은 경우에 시간복잡도를 제한에 맞추면 공간복잡도 역시 맞는 경우가 많으므로 굳이 더 다루지는 않겠다.

---

숙제)
다이나믹 프로그래밍(DP)의 예제와 숙제를 풀면서 작성한 코드의 시간복잡도 분석하기