입력 크기와 실행 시간의 관계. 실제 초를 재는 게 아니라 입력이 커질 때 연산 횟수가 어떤 모양으로 늘어나는지를 본다. 같은 알고리즘도 컴퓨터에 따라 걸리는 시간이 다르니, 기계와 무관하게 비교하려면 이 방법밖에 없다.
연산 세기와 증가율 순서
연산을 하나씩 세어 보면 감이 온다.
int func(int[] arr, int n) {
int cnt = 0; // 1번
for (int i = 0; i < n; i++) { // i 대입 1번, 반복마다 비교와 증가 2번
if (arr[i] % 5 == 0) cnt++; // 반복마다 나머지와 비교, 증가까지 3번
}
return cnt; // 1번
}전부 더하면 5n + 3이다. 모든 원소가 5의 배수인 최악을 잡은 값이다. n이 100만이면 500만이라 1초 안에 되지만 10억이면 50억이라 안 된다. n이 커질수록 앞의 5나 뒤의 3은 의미가 없어지고 n에 비례한다는 사실만 남는다. 그래서 상수와 낮은 차수를 버리고 O(n)이라고 쓴다.
증가율 순서는 이렇다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
로그가 나오면 밑이 2인 로그다. log 1024가 10 정도로 감을 잡아두면 계산이 빠르다.
최악을 재는 Big-O
Big-O, Big-Omega, Big-Theta가 있지만 실무에서든 코딩테스트에서든 대부분 Big-O를 쓴다. 최악의 경우를 포함한 상한이어서 최악이 통과하면 나머지도 다 통과하기 때문이다.
N명이 줄 서 있고 그중 “가나다”라는 사람을 찾는다고 하자. 이름을 물어보고 듣는 데 1초가 걸린다면, 아무 순서 없이 서 있을 때는 최선 1초, 최악 N초, 평균 N/2초다. 이름순으로 서 있으면 업다운 게임처럼 가운데 사람에게 물어볼 수 있어서 최악도 평균도 log N초로 떨어진다. 두 번째가 이분 탐색이고, N이 100만이어도 20번이면 끝난다.
1초 눈금과 그 예외
1초에 몇 번이나 연산하는지는 출처마다 다르게 잡는다. 바킹독은 3억에서 5억 번, 패스트캠퍼스는 약 1억 번을 기준으로 든다. 코딩테스트에서 시간 제한이 1초라면 최악의 입력에서도 그 안에 끝나야 한다.
어느 쪽이든 절대 기준이 아니라 감을 잡는 눈금이다. 상수가 크면 1천만 번이어도 1초를 넘길 수 있고, 최적화가 잘 되면 10억 번이어도 통과할 수 있다.
복잡도가 낮은 쪽이 늘 정답인 것도 아니다. 배열의 최댓값을 구한다면 반복문으로 훑어 O(n)에 끝낼 수도 있고, 정렬한 뒤 마지막을 꺼내 O(n log n)에 끝낼 수도 있다. 입력이 1000만이면 당연히 반복문이지만 입력이 작고 시간이 넉넉하면 한 줄로 끝나는 쪽이 낫다. 제한 안에 들어오는 것 중 가장 쓰기 쉬운 것을 고르는 일이다.