[1] 알고리즘 시간 측정

프로그래밍 대회의 시간 제한은 알고리즘의 시간 복잡도가 아니라 프로그램의 수행 시간을 기준으로 합니다. 따라서 어떤 알고리즘이 이 문제를 해결할 수 있을지 알기 위해서는 프로그램을 작성하기 전에 입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 있어야 합니다. 물론 프로그램의 수행 시간을 짐작하는 것은 엄청나게 어려운 일입니다. 프로그램의 동작 속도에 영향을 끼치는 요소는 입력의 크기와 시간 복잡도를 제외하고도 엄청나게 많기 때문입니다. CPU의 클록 속도, 1클록마다 수행할 수 있는 CPU 명령어의 수, 프로그램의 메모리 접근 패턴, 운영 체제와 컴파일러의 버전, ... 목록을 만들자면 끝이 없습니다.

그러나 많은 경우에는 시간 복잡도와 입력 크기만 알고 있더라도 어떤 알고리즘이 시간 안에 동작할지 대략적으로 짐작하는 것이 가능합니다. 시간 복잡도는 프로그램의 수행 시간에 가장 큰 영향을 미치는 요소이기 때문입니다. 앞에서 언급한 요소들은 프로그램의 수행 속도를 기껏해야 몇 배씩 차이나게 할 뿐입니다. 그러나 알고리즘의 시간 복잡도가 달라지면 프로그램은 수천 배, 수만 배까지 빨라지거나 느려질 수 있습니다.

입력의 최대 크기 N$N$이 10000이고, 테스트 케이스 하나를 푸는데 시간 제한이 1초인 문제를 풀고 있다고 가정합시다. 우리가 처음에 만든 알고리즘의 시간 복잡도가 O(N3)$O(N^3)$이라고 하면, 과연 이 알고리즘으로 시간 내에 문제를 풀 수 있을까요? O(N2)$O(N^2)$이나 O(NlgN)$O(N\lg N)$은 어떨까요? 이런 질문에 대답하기 위해 많은 프로그래밍 대회 참가자들이 사용하는 주먹구구 법칙은 다음과 같습니다.

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초 당 반복문 수행 횟수가 1억(108,)을 넘어가면 시간 제한을 초과할 가능성이 있다.1

이 기준을 이용해 앞의 경우 각 알고리즘을 시간 안에 실행할 수 있을지 판단해 봅시다. O(N3)$O(N^3)$ 알고리즘과 O(NlgN)$O(N\lg N)$ 알고리즘은 쉽게 판단할 수 있습니다. N3$N^3$에 10000을 대입하면 1억을 훨씬 초과하고, NlgN$N\lg N$에 10000을 대입하면 1억에 훨씬 미치지 못하기 때문이지요. 그런데 O(N2)$O(N^2)$ 알고리즘은 어떨까요? 1억을 초과하지 않으므로 시간 안에 실행될 거라고 말하고 싶지만, 경우에 따라 달라지기 때문에 프로그램을 직접 보기 전에는 뭐라고 말할 수 없습니다. 시간 복잡도와 입력의 크기 외의 요소들이 프로그램의 수행 속도를 열 배 정도는 쉽게 바꿔 놓을 수 있기 때문입니다. 이와 같이 이 법칙을 적용할 때는 충분한 여유를 두는 것이 좋습니다. 예를 들면 예측한 수행 횟수가 기준의 10% 이하인 경우와 기준의 10배를 넘는 경우에만 이 법칙을 적용하는 것이죠.

이렇게 각각 O(N3)$O(N^3)$, O(N2)$O(N^2)$, O(NlgN)$O(N\lg N)$, 그리고 O(N)$O(N)$의 시간 복잡도를 갖는 네 개의 알고리즘을 제시했습니다. 이제 각 알고리즘의 수행 시간을 짐작해 봅시다. 각 테스트 케이스별 시간 제한이 1초이고 N의 상한이 1,000, 10,000, 그리고 100,000일 때 이 중 어떤 알고리즘을 사용할 수 있을까요?

• ᆞN = 1,000: 이 때 N3$N^3$은 10억으로 주먹구구 법칙의 기준을 넘어서므로 ,O(N3)$O(N^3)$ 알고리즘을 사용할 때는 우선 주의하는 것이 좋습니다. 하지만 반복문의 내부가 아주 단순하기 때문에 아마도 시간 안에 수행할 수 있을 거라고 짐작됩니다. 다른 세 개의 더 빠른 알고리즘은 별 무리 없이 수행할 수 있겠지요.
• ᆞN = 10,000: 이때 N3$N^3$은 기준의 1만 배인 1조이므로 O (N3 ) 알고리즘은 시간 안에 돌아갈 가능성이 거의 없습니다. 반면 O(N2)$O(N^2)$은 어떨까요? 이때 N2$N^2$는 1억 정도이므로 주의해야 할 범위에 들어갑니다. 그러나 이 알고리즘의 반복문 내부도 엄청나게 단순하기 때문에 아마도 충분히 시간 안에 돌아갈 거란 생각이 듭니다. 그러면 그보다 빠른 두 알고리즘은 문제없이 수행되겠지요.
• ᆞN = 100,000: 이때는 N2$N^2$도 기준의 백 배인 100억이 됩니다. 따라서 O(N2)$O(N^2)$ 알고리즘도 시간 안에 돌아갈 가능성이 높지 않습니다. 반면 NlgN$N\lg N$는 대략 2천만 정도이므로 다른 두 알고리즘은 시간 안에 수월하게 돌아갈 겁니다.

[그림] 최대 연속 부분 구간 합 문제를 푸는 알고리즘의 속도 비교

• O(N3)$O(N^3)$ 알고리즘: 크기 2560인 입력까지를 1초 안에 풀 수 있습니다. 이때 25603은 대략 16억입니다.
• ᆞO(N2)$O(N^2)$ 알고리즘: 크기 40960인 입력까지를 1초 안에 풀 수 있습니다. 이때 409602은 대략 16억입니다.
• ᆞO(NlgN)$O(N\lg N)$ 알고리즘: 크기가 대략 2천만인 입력까지를 1초 안에 풀 수 있습니다. 이때 NlgN$N\lg N$은 대략 5억입니다.
• O(N)$O(N)$ 알고리즘: 크기가 대략 1억 6천만인 입력까지를 1초 안에 풀 수 있습니다.

출처 : http://book.algospot.com/estimation.html