본문 바로가기
Topos Uranos
한국어

알고리즘의 비용

요약

지금까지 이 강좌는 알고리즘을 단 하나의 물음으로 판단했다. 말한 대로 하는가? 이 수업은 두 번째 물음을 더한다. 올바른 프로그램이 실제로 쓸모 있는지를 결정하는 물음, 곧 비용이 얼마나 드는가? 이다. 비용은 먼저 시계 없이, 지배적 연산이 몇 번 실행되는지를 세어서 측정하며, 그 결과는 데이터 크기 nn의 함수가 된다. 이 함수에서 중요한 것은 주어진 nn에서의 값이 아니라 어떻게 증가하는가이다. nn, nlog⁡nn \log n, n2n^2, 2n2^n의 표를 보면, 알고리즘 사이의 차이는 데이터가 열 개일 때는 보이지 않지만 백만 개일 때는 깊은 골이 된다. OO 표기법은 이러한 증가 차수의 약칭으로, 형식적 정의 없이, 강좌에서 이미 본 예와 함께 소개된다. 유클리드 호제법은 로그, 벡터의 합은 선형, 모든 쌍의 비교는 이차, 단순한 피보나치는 지수이다. 이어서 <chrono>의 std::chrono::steady_clock 시계로 측정하고, 한 번의 측정이 왜 속이는지, 왜 최적화를 켜고 새니타이저 없이 측정하는지, 측정을 예측과 어떻게 대조하는지를 배운다. nn의 값을 두 배로 하면 선형 알고리즘은 시간이 두 배가 되고 이차 알고리즘은 네 배가 된다.

학습 목표

  1. 한두 겹의 반복문을 가진 알고리즘의 지배적 연산을 데이터 크기 nn의 함수로 셀 수 있다.
  2. 알고리즘을 상수, 로그, 선형, nlog⁡nn \log n, 이차 중 하나로 분류하고, nn의 값을 두 배로 할 때 그 시간이 어떻게 변하는지 예측할 수 있다.
  3. std::chrono::steady_clock 시계로 실행 시간을 측정하고, 측정을 예측과 비교할 수 있다.
  4. 주어진 데이터 크기에 대해 두 알고리즘 가운데 하나를 고르고, 그 선택을 증가 차수로 정당화할 수 있다.

연산 세기

두 번째 물음

올바른 반복문 설계 수업과 재귀 수업은 알고리즘이 올바르다는 것, 곧 종료하고 그 결과가 사후 조건을 만족한다는 것을 증명하는 법을 가르쳤다. 그런데 수치 알고리즘 수업은 똑같이 올바른 두 소수 판정을 보였다. 하나는 약 nn번의 나눗셈을, 다른 하나는 약 n\sqrt{n}번의 나눗셈을 한다. 또 재귀 수업은 F30F_{30}의 값을 계산하는 올바른 두 방법을 보였다. 하나는 2 692 5372\,692\,537번의 호출을, 다른 하나는 29번의 덧셈을 한다. 그렇다면 올바름만으로는 고를 수 없다. 올바른 두 알고리즘 가운데 하나는 순식간에 답하고, 다른 하나는 답이 의미를 잃기 전에 끝나지 않을 수도 있다. 그러므로 알고리즘에 던지는 두 번째 물음은 비용이 얼마나 드는가이다.

비용은 시계로 측정할 수도 있으며, 4절에서 그렇게 할 것이다. 그러나 한 번의 실행 시간은 기계, 컴파일러, 그 옵션, 그리고 같은 시각에 컴퓨터가 하고 있는 일에 달려 있으며, 그로부터는 다른 기계에서의 알고리즘에 대해 아무것도 따라 나오지 않는다. 그 어느 것에도 달려 있지 않은 것은 알고리즘이 밟는 단계의 수이다. 이로부터 이 수업의 첫 번째 결정이 따라 나온다. 비용은 세어서 측정하고, 시계는 그 셈을 확인하는 데 남겨 둔다.

크기와 지배적 연산

모든 단계(덧셈 하나하나, 비교 하나하나, 인덱스의 증가 하나하나, 메모리 접근 하나하나)를 세는 것은 번거롭고 쓸모없다. 거의 모두가 일정한 비율로 하나의 주된 단계에 따라붙기 때문이다. 그러므로 지배적 연산을 고른다. 상수배를 제외하면 다른 어떤 연산보다 적지 않게 실행되고, 그래서 모두를 대표하는 연산이다. 벡터 원소의 합에서는 덧셈, 최댓값 찾기에서는 비교, 소수 판정에서는 나눗셈이 그것이다. 그것이 실행되는 횟수는 입력 크기의 함수로 나타내며, 그 기호는 nn이다. 곧 벡터의 원소 수, 판정하는 수, 자릿수 등이다.

nn개의 원소로 이루어진 벡터를 순회하며 각 원소에 일정한 양의 일을 하는 단순한 반복문은 지배적 연산을 nn번 실행한다. 반면 비어 있지 않은 벡터의 최댓값은 첫 원소를 후보로 삼아 시작하고 나머지 원소를 하나씩 후보와 비교한다. 비교는 n−1n - 1번이다. nn, n−1n - 1 사이의 차이는 실재하지만, 3절에서 보겠지만 중요한 것은 아무것도 바꾸지 않는다.

최악의 경우

같은 크기의 데이터에서 언제나 같은 횟수의 연산을 실행하지는 않는 알고리즘도 있다. 벡터에서 값을 찾되 찾을 때까지 순회하는 탐색은, 값이 첫 위치에 있으면 비교를 한 번만 하고, 없으면 nn번 한다. 그 비용을 말하려면 두 상황 가운데 하나를 고르는데, 보통의 선택은 최악의 경우, 곧 크기가 nn인 모든 입력 가운데 연산 횟수의 최댓값이다. 이유는 계약이 사전 조건을 만족하는 모든 입력에 대해 쓰이는 것과 같다. 최악의 경우는 보장이고, 최선의 경우는 희망일 뿐이다. 그래서 선형 탐색의 비용은 최악의 경우 nn번의 비교이며, 이 수업이 단서 없이 “비용”이라고 할 때는 최악의 경우의 비용을 말한다.

중첩 반복문

반복문 수업은 중첩된 두 반복문의 회차를 세는 법을 가르쳤다. 안쪽 반복문이 언제나 mm회를 돌고, 바깥쪽의 nn회 각각에 대해 그렇다면, 안쪽 본체는 n⋅mn \cdot m번 실행된다. 안쪽이 바깥쪽에 의존하면 행별로 더한다. 컬렉션을 다룰 때 가장 자주 나타나는 경우는 모든 쌍이다. 각 원소를 그 뒤에 오는 원소 하나하나와 비교하는 것으로, 벡터에 중복이 있는지 찾을 때가 그렇다.

C++ 프로그램
#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}: 비교 {:>10}회; n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}
출력
n =     10: 비교         45회; n(n - 1)/2 = 45n =    100: 비교       4950회; n(n - 1)/2 = 4950n =   1000: 비교     499500회; n(n - 1)/2 = 499500n =  10000: 비교   49995000회; n(n - 1)/2 = 49995000

카운터는 실제 알고리즘이 할 비교의 자리를 차지한다. 바깥쪽의 ii번째 회차에서 안쪽은 i+1i + 1부터 n−1n - 1까지 가며 n−1−in - 1 - i회를 돈다. 따라서 합계는 (n−1)+(n−2)+⋯+1+0(n - 1) + (n - 2) + \cdots + 1 + 0의 값이며, 이는 반복문 수업의 합이다:

∑i=0n−1(n−1−i)=n(n−1)2\sum_{i=0}^{n-1} (n - 1 - i) = \frac{n(n - 1)}{2}

출력은 모든 크기에 대해 이 공식을 확인해 준다. 카운터가 long long 타입인 것은 nn의 값이 약 육만 오천을 넘으면 쌍의 수가 int 타입(이 플랫폼에서는 32비트)의 최댓값을 넘기 때문이며, 공식이 변환한 뒤에 곱하는 것도 같은 이유에서이다. 이차 알고리즘의 카운터는 데이터보다 훨씬 먼저 오버플로가 난다.

3절에서 일반화할 것을 지금 미리 보아 두자. nn의 값을 10배 하면 비교 횟수는 약 100배가 된다. 데이터가 열 개면 비교 45번, 만 개면 거의 오천만 번이다.