프로그램이 얼마나 오래 걸리는지를 시계로 재면 컴퓨터마다 답이 다르다. 그래서 시계 대신 “일을 몇 번 하는가”를 입력 크기가 들어간 식으로 센다. 가장 자주 하는 일 한 가지만 골라 세면 쉽지만 나머지 줄에 쓴 시간이 빠지고, 모든 줄을 다 세면 빠짐이 없지만 손이 많이 간다. 크기가 같은 입력이라도 값이 놓인 순서에 따라 횟수가 달라지므로, 가장 많이 드는 경우와 가장 적게 드는 경우를 따로 센다.
예시로 보기
같은 프로그램을 내 노트북에서 재면 2초, 서버에서 재면 0.3초가 나올 수 있다. 이 숫자로는 방법 자체가 좋은지 알 수 없다. 기계와 상관없는 잣대가 필요하다.
잣대로 쓸 프로그램은 삽입 정렬이다. 카드 패를 왼쪽부터 정리하듯, a[i]를 이미 정렬된 앞부분 a[0..i-1] 안의 제자리에 끼운다. 정렬 방법 자체는 삽입 정렬에서 다룬다.
void insertion_sort(int a[], int n)
{
int i;
for (i = 1; i < n; i++) {
/* a[i]를 이미 정렬된 a[0..i-1] 안의 제자리에 끼운다 */
int t = a[i];
int j;
for (j = i - 1; j >= 0 && t < a[j]; j--)
a[j + 1] = a[j];
a[j + 1] = t;
}
}
안쪽 for는 끼울 값 t보다 큰 값을 한 칸씩 오른쪽으로 민다. t보다 크지 않은 값을 만나거나 배열 맨 앞을 지나면 멈춘다.
길이가 4인 두 입력에서 비교 t < a[j]를 몇 번 계산하는지 센다1.
바퀴 i |
끼울 값 t |
비교 횟수 | 바퀴가 끝난 뒤 |
|---|---|---|---|
| 처음 | 4 3 2 1 | ||
| 1 | 3 | 1 | 3 4 2 1 |
| 2 | 2 | 2 | 2 3 4 1 |
| 3 | 1 | 3 | 1 2 3 4 |
거꾸로 놓인 4 3 2 1은 비교를 \(1 + 2 + 3 = 6\)번 한다. 이미 정렬된 1 2 3 4는 바퀴마다 한 번만 비교하고 멈춰서 3번이다. 길이는 둘 다 4인데 횟수가 두 배다. 그래서 “길이 4일 때 몇 번”이 아니라 “길이 4일 때 많으면 몇 번, 적으면 몇 번”이라고 말해야 한다.
무엇을 세는가
프로그램의 비용은 둘로 잰다.
- 공간. 프로그램이 차지하는 메모리의 양이다. 바이트, KB, MB, GB로 잰다.
- 시간. 실행에 걸리는 시간이다. 보통 실행 횟수로 잰다. 세는 법은 세 가지다. 연산 한 가지를 골라 세기, 단계 수 세기, 입력이 커질 때의 빠르기만 적기(\(O(n)\), \(O(n^2)\) 같은 표기).
횟수는 입력의 크기를 나타내는 수의 식으로 적는다. 이 수를 인스턴스 특성(instance characteristic)이라 부른다. 삽입 정렬에서는 배열의 길이 \(n\)이다.
한 가지 연산만 세기
가장 자주 하는 연산 하나를 고른다. 삽입 정렬에서는 비교 t < a[j]다. 비교 횟수는 i뿐 아니라 배열의 값과 t에 따라서도 달라진다. 그래서 세 가지를 따로 말한다.
- 최악의 경우(worst case): 가장 많이 드는 횟수
- 최선의 경우(best case): 가장 적게 드는 횟수
- 평균(average)
최악. 앞부분이 [1, 2, 3, 4]이고 t = 0이면 네 값이 모두 t보다 커서 4번 비교한다. 앞부분이 [1, 2, …, i]이고 t = 0이면 i번이다. 바퀴마다 이렇게 되면 전체 비교 횟수는 1부터 \(n - 1\)까지의 합이다.
\(n = 4\)를 넣으면 \(\frac{3 \times 4}{2} = 6\)이다. 위 표의 6번과 같다. 합을 이렇게 묶는 법은 수열과 합의 기호에 있다.
최선. 이미 정렬된 입력에서는 t가 바로 앞의 값보다 작지 않아 바퀴마다 한 번 비교하고 멈춘다. 바퀴가 \(n - 1\)번이니 \(n - 1\)번이다1.
평균. 모든 순서가 같은 확률로 온다고 치면 평균 비교 횟수는 \(\frac{n(n-1)}{4} + n - H_n\)이다. 여기서 \(H_n = 1 + \frac12 + \dots + \frac1n\)이다. \(n\)이 크면 최악의 절반쯤이다1.
t가 앞부분의 모든 값보다 작으면 j가 \(-1\)이 되어 반복이 끝난다. 이때는 j >= 0이 거짓이라 t < a[j]를 계산하지 않는다. &&는 앞쪽이 거짓이면 뒤쪽을 보지 않기 때문이다. 그래서 i번째 바퀴의 비교는 많아야 i번이지, i + 1번이 아니다1.
모든 줄 세기
비교만 세면 값을 옮기는 줄과 t를 넣는 줄에 쓴 시간이 빠진다. 단계 수 세기는 프로그램의 모든 부분에 쓴 시간을 센다.
단계(step)는 입력 크기 \(n\)과 상관없는 양의 계산이다. 얼마나 많은지가 아니라 \(n\)에 따라 늘어나는지를 본다.
- 덧셈 10번, 뺄셈 100번, 곱셈 1,000번은 모두 한 단계로 쳐도 된다. \(n\)이 커져도 그대로이기 때문이다.
- 덧셈 \(n\)번은 한 단계로 칠 수 없다. \(n\)이 커지면 함께 늘어난다.
줄마다 “한 번 실행할 때 몇 단계인가”를 먼저 적는다. 이 값을 s/e(steps per execution)라 부른다. 그다음 그 줄을 몇 번 실행하는지 세어 곱한다. 아래 횟수는 최악의 경우, i번째 바퀴 한 번의 값이다.
| 줄 | s/e | i번째 바퀴에서 실행 횟수 |
|---|---|---|
for (i = 1; i < n; i++) |
1 | (아래에서 따로 센다) |
{ |
0 | |
int t = a[i]; |
1 | 1 |
int j; |
0 | |
for (j = i - 1; j >= 0 && t < a[j]; j--) |
1 | \(i + 1\) |
a[j + 1] = a[j]; |
1 | \(i\) |
a[j + 1] = t; |
1 | 1 |
} |
0 |
안쪽 for의 머리줄은 값을 i번 옮기는 동안 i번, 끝났음을 알아채는 데 한 번 더 실행된다. 그래서 \(i + 1\)번이다.
바퀴 하나의 단계 수는 \(1 + (i + 1) + i + 1 = 2i + 3\)이다. 전체는 다음과 같다.
- 바깥
for의 머리줄:i = 1, 2, …, n에서 한 번씩 검사하니 \(n\)번이다. 마지막 검사는 거짓이 되어 반복을 끝낸다. - 반복의 몸통: 바퀴마다 \(2i + 3\)을 \(i = 1\)부터 \(n - 1\)까지 더한다.
둘을 더한 최악의 단계 수는 \(n + (n - 1)(n + 3) = n^2 + 3n - 3\)이다. \(n = 4\)를 넣으면 \(4 + 3 \times 7 = 25\)다.
이미 정렬된 입력에서는 안쪽 머리줄이 바퀴마다 한 번, 옮기는 줄이 0번이다. 바퀴 하나가 3단계라서 최선의 단계 수는 \(n + 3(n - 1) = 4n - 3\)이다1.
s/e가 0이나 1이 아닌 줄. x = sum(a, n);에서 sum이 a[0..n-1]을 모두 더하는 함수면, 이 한 줄의 s/e는 \(n\)이다. 한 줄이라고 한 단계가 아니다. 함수 안에서 하는 일이 \(n\)에 따라 늘어나기 때문이다.
식에서 큰 그림으로
삽입 정렬의 복잡도는 \(O(n^2)\)이다. 뜻은 이렇다. \(n\)이 알맞게 크면, 크기 \(n\)인 어떤 입력에서도 시간(또는 연산 횟수)이 \(c \cdot n^2\)을 넘지 않는다. \(c\)는 \(n\)과 상관없는 수다. 위에서 구한 \(n^2 + 3n - 3\)은 \(n \ge 1\)이면 \(4n^2\)을 넘지 않는다.
더 정확히는 최악의 시간이 \(\Theta(n^2)\), 최선의 시간이 \(\Theta(n)\)이다. 그래서 \(n\)이 두 배가 될 때마다 최악의 시간은 네 배가 된다고 내다본다. 식으로 확인하면 \(n = 100\)일 때 10,297단계, \(n = 200\)일 때 40,597단계로 3.94배다. \(O\)와 \(\Theta\)의 정확한 뜻은 점근 표기에 있다.
이 차이가 실제로 얼마나 큰지는 시간으로 바꿔 보면 드러난다. 1초에 명령 \(10^9\)개를 실행하는 기계에서 걸리는 시간이다.
| \(n\) | \(n\) | \(n \log_2 n\) | \(n^2\) | \(n^3\) |
|---|---|---|---|---|
| 1,000 | 1마이크로초 | 10마이크로초 | 1밀리초 | 1초 |
| 10,000 | 10마이크로초 | 130마이크로초 | 100밀리초 | 17분 |
| \(10^6\) | 1밀리초 | 20밀리초 | 17분 | 32년 |
값이 백만 개일 때 \(n \log_2 n\) 방법은 눈 깜짝할 사이에 끝나고 \(n^2\) 방법은 17분이 걸린다. 그래서 기계를 빠르게 바꾸는 것보다 방법을 고치는 쪽이 훨씬 쓸모 있다. 예를 들어 \(2^n\) 방법을 \(n^3\) 방법으로 바꾼다고 하자. \(n = 60\)이면 \(2^n\) 방법은 같은 기계에서 36년쯤 걸리고, \(n^3\) 방법은 0.2밀리초에 끝난다2.
활용
- 어느 쪽을 쓰나. 한 가지 연산만 세는 방법은 그 연산이 일의 대부분일 때 쓴다. 정렬과 탐색에서 비교 횟수를 세는 것이 그런 경우다. 줄마다 하는 일이 고르게 퍼져 있으면 단계 수를 센다.
- 흔한 실수.
for의 머리줄을 반복 횟수만큼만 세는 것이다. 끝났음을 알아채는 검사가 한 번 더 있다. 또 함수를 부르는 한 줄을 늘 한 단계로 치는 것이다. - 연습: 단계 수 세기 예제 사다리
- 코드를 짜기 전에 자릿수만 어림하는 법: 시간 복잡도로 방법 고르기
연결
- 선수: 자료구조란, 수열과 합의 기호
- 센 식에서 가장 큰 항만 남기는 표기: 점근 표기
- 한 번은 비싸도 여러 번을 합치면 싼 경우를 세는 법: 배열 두 배 늘리기
확인 문제
C1 a = [3, 1, 2]를 위 삽입 정렬로 정렬한다. 바퀴마다 비교 t < a[j]를 몇 번 계산하는가? 바퀴가 끝난 뒤의 배열도 쓰라.
답: 1번째 바퀴(t = 1): 1번, 배열은 1 3 2. 2번째 바퀴(t = 2): 2번, 배열은 1 2 3. 모두 3번이다.
이유: 1번째 바퀴는 3과 한 번 비교해 3을 밀고, j가 \(-1\)이 되어 비교 없이 끝난다. 2번째 바퀴는 3과 비교해 밀고(참), 1과 비교해 멈춘다(거짓).
C2 최악의 경우 i번째 바퀴에서 안쪽 for의 머리줄은 \(i + 1\)번 실행되는데, 비교 t < a[j]는 왜 i번만 계산하는가?
답: 마지막 실행에서는 j가 \(-1\)이라 j >= 0이 거짓이고, &&는 앞쪽이 거짓이면 뒤쪽 t < a[j]를 계산하지 않기 때문이다.
이유: 머리줄의 실행 횟수는 “조건을 검사한 횟수”이고 비교 횟수는 “t < a[j]를 실제로 계산한 횟수”다. 세는 대상이 다르다.
C3 덧셈 1,000번은 한 단계로 쳐도 되는데 덧셈 \(n\)번은 왜 한 단계로 칠 수 없는가? 한 가지 연산만 세는 방법과 단계 수를 세는 방법의 차이도 한 문장으로 쓰라.
답: 단계는 입력 크기 \(n\)과 상관없는 양의 계산이다. 1,000번은 \(n\)이 커져도 1,000번이지만 \(n\)번은 \(n\)과 함께 늘어난다. 한 가지 연산만 세는 방법은 고른 연산 말고는 세지 않고, 단계 수를 세는 방법은 프로그램의 모든 부분을 센다.
흔한 오답: “1,000은 작은 수라서.” 크기가 아니라 \(n\)에 따라 변하는지가 기준이다. 100만 번이라도 \(n\)과 상관없으면 한 단계다.