코드의 시간복잡도에 따른 실제 수행시간 예측하기

여러 코딩 테스트나 코딩 문제를 풀다가, 혹은 자신의 프로그램의 최적화를 위해 공부하다보면 빅오표기법이나 시간복잡도같은 여러 단어들을 접해봤을 것이다. 예를 들어서 단순한 for문은 $O(N)$, 이중 for문은 $O(N^2)$의 시간복잡도를 가지고 있다. 어떤 알고리즘은 $O(N log N)$이고, 어떤 알고리즘은 $O(N^2)$고, 어떤건 $O(N)$이고… 대충 $O(N)$은 $O(N^2)$보다 빠른건 알겠는데, 이게 내가 직면한 문제를 풀 때 $O(N^2)$보다 빠르다고 해서 그 알고리즘을 써도 되는가?하면 그것도 아닐 수 있다는 것이다. 그러면 대략적인 수행시간을 예측해야하는데, 보통은 계산할 때 대략 이 정도의 생각을 둔다.

1. 알고리즘의 시간복잡도
2. 코드가 수행할 범위
3. 평균 1억 = 1초

모두가 이 정도의 생각은 하며 코딩을 할 것이다. 이 때 3. 평균 1억 = 1초라는게 좀 의아할 수도 있는데, 사람마다 코드를 짜는 컴퓨터가 제각각이고 날마다 발전하는 컴퓨터 사양이 있는데 1억 = 1초라는게 공통적으로 가능하다고? 물론 생각하는 것처럼 정말 느린 컴퓨터면 1억의 수행 횟수를 못 할수도, 최신 사양의 컴퓨터라면 1초이내로도 충분히 1억의 연산 횟수를 수행할 수 있을 것이다. 또 아주 단순한 연산을 반복하면 1억번에 1초도 걸리지 않고 연산을 수행할 것이다. 하지만 시간복잡도는 최악을 가정한다. 복잡한 연산을 수행할 때도 있을 것이기 때문에 계산하기 편하게 O(1억) = 1초 라고 생각하자~ 라고 보면 된다.

그리고 시간복잡도에 따른 1초 당 입력의 최대 크기(명령 수행 가능 횟수)는 보통 이렇다.

• $O(logN)$ = 약 1억
• $O(N)$ = 약 1억
• $O(NlogN)$ = 약 500만
• $O(N^2)$ = 약 1만
• $O(N^3)$ = 약 500
• $O(2^N)$ = 약 20
• $O(N!)$ = 약 10

$O(N^2)$부터 급격하게 효율이 떨어지는걸 볼 수 있는데, 이 비효율적인 시간복잡도는 프로그램이 복잡해질수록, 프로그램이 커질수록 더욱 더 크게 나타낸다. 그래서 최대한 $O(N^2)$ 아래의 알고리즘을 피하고 가능한 $O(NlogN)$위의 알고리즘을 사용해서 문제를 해결하는게 바람직하다고 볼 수 있다.