입력 크기·O·Ω·Θ와 정보의 개수

"이 프로그램은 빠르다"는 말은 생각보다 많은 것을 알려 주지 않습니다. 입력이 10개일 때 빨랐던 프로그램이 입력 1만 개에서는 견딜 수 없이 느려지기도 하고, 작은 입력에서 조금 느렸던 프로그램이 큰 입력에서는 훨씬 앞서기도 합니다. 그래서 알고리즘의 비용은 "입력이 커질 때 얼마나 빨리 늘어나는가"로 비교합니다. 이 글에서는 그 빠르기를 나타내는 O, Ω, Θ 표기를 정의부터 익히고, 반으로 나누는 방법이 왜 로그 규모가 되는지 확인합니다. 마지막으로 후보 여러 개를 구별하는 데 정보가 얼마나 필요한지 비트로 계산합니다. 로그를 미리 알 필요는 없고, 2를 거듭해서 곱하는 계산만 할 수 있으면 됩니다.

입력 크기와 비용 함수

비용을 이야기하려면 먼저 입력의 크기를 무엇으로 잴지 정해야 합니다. 리스트를 다루는 알고리즘이라면 보통 원소의 개수를 n으로 둡니다. 그다음 입력 크기가 n일 때 알고리즘이 수행하는 기본 단계의 수를 함수 T(n)으로 나타냅니다. 비교 한 번, 대입 한 번, 작은 정수의 덧셈 한 번처럼 입력 크기와 상관없이 일정한 시간이 드는 연산을 각각 한 단계로 셉니다.

같은 크기의 입력이라도 내용에 따라 단계 수가 다를 수 있다는 점에 주의해야 합니다. 순차 탐색은 목표가 맨 앞에 있으면 비교 한 번으로 끝나지만, 목표가 없으면 n번을 모두 비교합니다. 그래서 비용 함수를 말할 때는 어떤 경우의 비용인지를 함께 밝힙니다. 가장 오래 걸리는 입력에서의 비용을 최악의 경우(worst case), 가장 빨리 끝나는 입력에서의 비용을 최선의 경우(best case)라고 합니다.

상수보다 증가율이 중요한 이유

두 알고리즘의 비용이 각각 5n 단계와 n² 단계라고 해 봅시다. 작은 입력에서는 어느 쪽이 빠른지 직접 계산해 보면 됩니다.

for n in [4, 5, 6, 100]:
    print(n, 5 * n, n * n)

4 20 16
5 25 25
6 30 36
100 500 10000

n이 4일 때는 n²쪽이 16단계로 더 적습니다. n이 5일 때 둘은 같아지고, 6부터는 n²쪽이 더 많아지며, n이 100이면 20배나 차이가 납니다. 5n은 n이 두 배가 되면 두 배로 늘지만, n²은 네 배로 늘기 때문입니다. 작은 입력에서 잰 순서가 큰 입력에서도 유지된다는 보장은 없습니다. 그래서 상수 5처럼 구현과 컴퓨터에 따라 달라지는 값보다, n이 커질 때 늘어나는 모양인 증가율(growth rate)을 먼저 봅니다.

O, Ω, Θ의 뜻

증가율을 나타내는 표기는 세 가지입니다. T(n) = O(g(n))은 n이 충분히 클 때 T(n)이 g(n)의 상수배를 넘지 않는다는 뜻으로, 위쪽 한계인 상한(upper bound)을 말합니다. T(n) = Ω(g(n))은 n이 충분히 클 때 T(n)이 g(n)의 상수배보다 작아지지 않는다는 뜻으로, 아래쪽 한계인 하한(lower bound)을 말합니다. 둘이 함께 성립하면 T(n) = Θ(g(n))이라 쓰고, T(n)이 g(n)과 같은 규모로 늘어난다고 말합니다. 각각 "빅오", "빅오메가", "빅세타"라고 읽습니다.

"충분히 클 때"와 "상수배"를 정확한 말로 바꾸면 다음과 같습니다. 양의 상수 C와 시작점 n₀가 있어서, n₀ 이상인 모든 n에서 T(n) ≤ C × g(n)이 성립하면 T(n) = O(g(n))입니다. 여기서 중요한 것은 C와 n₀를 먼저 하나 정한 뒤에는 n이 커져도 바꾸지 않는다는 점입니다. n마다 다른 C를 고를 수 있다면 어떤 함수든 상한을 만들 수 있어서 표기가 아무 뜻도 갖지 못합니다. Ω는 부등식의 방향이 반대입니다. 양의 상수 c와 시작점이 있어서 그 이상인 모든 n에서 c × g(n) ≤ T(n)이 성립하면 T(n) = Ω(g(n))입니다.

T(n) = 3n + 7로 연습해 보겠습니다. n ≥ 1이면 7 ≤ 7n이므로 3n + 7 ≤ 3n + 7n = 10n입니다. 따라서 C = 10, n₀ = 1로 두면 상한의 조건이 성립하고, T(n) = O(n)입니다. 또 n ≥ 1인 모든 n에서 3n ≤ 3n + 7이므로 c = 3으로 하한의 조건도 성립하고, T(n) = Ω(n)입니다. 두 결과를 합치면 T(n) = Θ(n)입니다. 이때의 상수는 하나로 정해지지 않습니다. C = 4, n₀ = 7도 상한의 조건을 만족합니다. n ≥ 7이면 7 ≤ n이라서 3n + 7 ≤ 4n이기 때문입니다. 필요한 것은 조건을 만족하는 상수가 적어도 한 쌍 있다는 사실뿐입니다.

몇 개의 n으로 실행해 본 결과만으로는 이런 부등식을 증명할 수 없습니다. 정의가 요구하는 것은 n₀ 이상인 모든 n이기 때문입니다. 형식적인 정의는 Cornell 대학교의 점근 분석 강의 노트에서도 확인할 수 있습니다.

표기와 "최악·최선"은 다른 이야기다

O를 "최악의 경우", Ω를 "최선의 경우"와 같은 말로 생각하기 쉽지만 둘은 따로 정하는 것입니다. 먼저 어떤 경우의 비용 함수인지 정하고, 그 함수에 대해 상한과 하한을 말합니다. 순차 탐색의 최악의 경우 비용은 n번의 비교이므로 Θ(n)이고, 최선의 경우 비용은 비교 한 번이므로 Θ(1)입니다. 최악의 경우에도 Θ가 있고 최선의 경우에도 Θ가 있는 것입니다.

"순차 탐색은 O(n)이다"라고 경우를 밝히지 않고 말할 때는, 어떤 입력이 들어와도 비용이 n의 상수배를 넘지 않는다는 뜻으로 받아들이면 됩니다. 이 문장은 참이지만, 같은 이유로 "순차 탐색은 O(n²)이다"도 참입니다. n의 상수배를 넘지 않는 값은 n²의 상수배도 넘지 않기 때문입니다. 상한은 느슨하게 말해도 틀리지 않으므로, 비용의 규모를 정확히 알리고 싶다면 Θ와 그 근거를 함께 제시해야 합니다.

반으로 줄이면 로그, 두 겹이면 제곱

비용 함수에서 가장 자주 보는 모양은 반복의 구조에서 나옵니다. 남은 범위를 매번 절반으로 줄이는 반복은 몇 번 만에 범위를 1로 만들까요? 범위의 크기를 절반으로 줄이되 홀수면 올림한다고 하고, 1이 될 때까지 세어 봅니다.

def halving_steps(n):
    steps = 0
    while n > 1:
        n = (n + 1) // 2
        steps += 1
    return steps


for n in [10, 100, 1000]:
    print(n, halving_steps(n), n * n)

10 4 100
100 7 10000
1000 10 1000000

n이 10배씩 커지는 동안 절반으로 줄이는 횟수는 4, 7, 10으로 3씩 늘어날 뿐입니다. 2를 k번 곱한 수 2ᵏ이 n 이상이 되는 가장 작은 k가 바로 이 횟수입니다. 2ˣ = n을 만족하는 수 x를 밑이 2인 로그(logarithm)라 하고 log₂ n이라고 씁니다. n이 2의 거듭제곱이면 log₂ n은 2를 곱한 횟수 그대로이지만, log₂ 10이 약 3.32인 것처럼 정수가 아닐 수도 있으므로 이 횟수는 log₂ n을 올림한 값입니다. 2¹⁰이 1,024이므로 1,000 정도의 범위는 열 번이면 하나로 줄어듭니다. 반면 n개의 원소마다 다시 n개를 훑는 두 겹의 반복은 n × n번 돌아서, 셋째 열처럼 n이 10배가 될 때마다 100배씩 늘어납니다. 반으로 줄이는 탐색은 Θ(log n), 두 겹의 반복은 Θ(n²)가 되는 이유가 이것입니다.

후보를 구별하는 데 필요한 정보

로그는 정보의 양을 셀 때도 나타납니다. 켜짐과 꺼짐, 두 상태만 갖는 센서가 k개 있다고 해 봅시다. 센서 하나는 두 가지를 구별하고, 두 개는 2 × 2 = 4가지, k개는 2ᵏ가지 조합을 만듭니다. 그러므로 후보 n개에 서로 다른 신호를 하나씩 주려면 2ᵏ ≥ n을 만족하는 가장 작은 k개의 센서가 필요합니다. 켜짐을 1, 꺼짐을 0으로 적으면 각 조합은 0과 1로 된 k자리 코드이고, 이 한 자리를 비트(bit)라고 합니다.

후보가 하나뿐이면 구별할 상대가 없으므로 비트가 하나도 필요 없습니다. 후보 5개에는 두 비트로 만드는 4가지 조합이 모자라서 세 비트가 필요하고, 000, 001, 010, 011, 100처럼 8가지 조합 가운데 5개만 쓰면 됩니다. 모든 조합을 다 쓸 필요는 없습니다. 이 계산은 정보의 양을 따지는 모델일 뿐이고, 실제 센서의 오차나 동작 방식은 따로 설계해야 한다는 점도 덧붙여 둡니다.

이 계산을 Python으로 옮깁니다. 후보에 0부터 n-1까지 번호를 붙이면, 가장 큰 번호 n-1을 이진수로 적는 데 필요한 자릿수가 곧 필요한 비트 수입니다.

def sensor_codes(count):
    if count < 1:
        raise ValueError("positive item count required")
    width = (count - 1).bit_length()
    return width, [format(i, f"0{width}b") if width else "" for i in range(count)]


print(sensor_codes(5))
print(sensor_codes(1))

(3, ['000', '001', '010', '011', '100'])
(0, [''])

bit_length()는 정수를 이진수로 적었을 때 부호와 앞쪽의 0을 뺀 자릿수를 돌려주므로, 0에는 0을 돌려줍니다. 4는 이진수로 100이므로 (5 - 1).bit_length()는 3입니다. format(i, f"0{width}b")는 번호 i를 이진수 문자열로 바꾸되, 앞을 0으로 채워 width 자리로 맞춥니다. f"..."는 중괄호 안의 값을 문자열에 넣어 주는 f-문자열이라서, width가 3이면 형식 문자열은 "03b"가 되고 끝의 b는 이진수로 표시하라는 뜻입니다. 후보가 하나면 width가 0이므로 빈 문자열 하나를 코드로 씁니다. A if 조건 else B는 조건이 참이면 A를, 거짓이면 B를 값으로 고르는 조건 표현식(conditional expression)입니다. 1장에서 본 컴프리헨션 끝의 if는 원소를 걸러 내지만, 이 식은 원소마다 두 값 가운데 하나를 고를 뿐이라 결과는 언제나 count개입니다. 함수는 비트 수와 코드 목록 두 값을 괄호로 묶은 튜플(tuple)로 돌려주는데, 튜플은 순서가 있고 만든 뒤에는 바꿀 수 없는 값의 묶음입니다.

이 코드가 맞는 이유는 간단합니다. 0부터 n-1까지의 서로 다른 정수는 이진 표현도 서로 다르고, 가장 큰 번호 n-1이 들어가는 자릿수라면 그보다 작은 번호도 모두 들어갑니다. 그래서 코드는 겹치지 않고 모두 같은 길이를 가집니다. 반복은 range(count)의 n번만 돌고 끝납니다.

더 깊이: 결과가 세 가지인 시험

이 생각은 정보를 얻는 방법이 바뀌어도 그대로 쓸 수 있습니다. 한 번의 시험이 b가지 결과를 줄 수 있다면, 시험 k번으로 구별할 수 있는 경우는 최대 bᵏ가지입니다. 앞에서 본 저울은 왼쪽이 가볍다, 오른쪽이 가볍다, 균형이 맞는다의 세 가지 결과를 주므로, 가짜 동전 16개를 구별하려면 3ᵏ ≥ 16이어야 하고 k는 적어도 3입니다. 3² = 9로는 모자라고 3³ = 27이면 충분하기 때문입니다. 실제로 세 묶음으로 나누는 방법이 세 번 만에 찾아내므로, 이 경우에는 그 하한을 그대로 달성합니다.

비교만으로 정렬하는 알고리즘의 한계도 같은 방식으로 구합니다. 서로 다른 값 n개를 늘어놓는 순서는 n! = n × (n-1) × … × 1가지이고, 비교 한 번은 "크다" 또는 "작다"의 두 결과만 줍니다. 그래서 어떤 비교 정렬도 최악의 경우 적어도 log₂(n!)번은 비교해야 하며, 이 값은 대략 n log₂ n 규모입니다. 필요한 정보의 양이 비용의 하한이 되는 것입니다.

출력의 크기도 비용이다

필요한 비트 수 k를 구하는 일은 bit_length() 한 번이면 끝납니다. 하지만 코드 전체를 만드는 데는 그보다 훨씬 많은 일이 듭니다. 문자열 n개를 각각 k자리로 만들어야 하므로 출력의 글자 수가 n × k이고, 비용도 Θ(nk)입니다. k가 log n 규모라고 해서 코드를 모두 만드는 일까지 O(log n)인 것은 아닙니다. 결과를 모두 적어야 하는 문제는 결과의 크기보다 빨리 끝날 수 없습니다.

또 이 교재는 비교나 덧셈 같은 연산을 한 단계로 세는데, 이것은 컴퓨터가 한 번에 다룰 수 있는 크기의 수에만 맞는 가정입니다. Python은 아주 큰 정수도 다룰 수 있지만, 수백 자리 정수끼리의 곱셈이나 긴 문자열끼리의 비교는 자릿수나 길이에 비례하는 시간이 듭니다. 그런 연산이 중심이 되는 문제에서는 그 비용을 따로 표시합니다.

O(1)은 1초가 아니다

O(1)은 실행 시간이 1초라는 뜻이 아니라, 입력이 커져도 비용이 일정한 값을 넘지 않는다는 뜻입니다. O 표기는 증가율만 말하기 때문에 상수배를 감춥니다. 그래서 실제로 측정한 시간은 상수, 컴퓨터의 성능, 프로그래밍 언어, 입출력 방식에 따라 얼마든지 달라질 수 있습니다. 증가율은 입력이 커질 때 어떤 일이 생길지 알려 주고, 실제 측정은 지금 이 환경에서 얼마나 걸리는지 알려 줍니다. 둘은 서로를 대신하지 않으므로 함께 봐야 합니다.

정리

• 비용을 말하려면 입력 크기 n을 무엇으로 잴지와 어떤 경우의 비용인지 먼저 정하고, 기본 단계의 수를 비용 함수 T(n)으로 나타냅니다.
• O(g(n))은 상한, Ω(g(n))은 하한이며, 둘이 함께 성립하면 Θ(g(n))입니다. 정의의 상수 C와 시작점 n₀는 한 번 정하면 n에 따라 바꾸지 않습니다.
• O, Ω, Θ는 최악·최선의 경우와 같은 말이 아닙니다. 순차 탐색은 최악의 경우 Θ(n), 최선의 경우 Θ(1)입니다.
• 범위를 매번 절반으로 줄이면 약 log₂ n번 만에 끝나고, n번씩 두 겹으로 반복하면 n²번 돕니다.
• 후보 n개를 비트로 구별하려면 2ᵏ ≥ n인 가장 작은 k비트가 필요합니다. 결과가 b가지인 시험이라면 bᵏ ≥ n이어야 합니다.

연습 문제

1. 후보 9개를 구별하는 비트

후보 9개에 서로 다른 코드를 주려고 합니다. 세 비트로 충분할까요? 필요한 최소 비트 수를 구하세요.

print((9 - 1).bit_length())

4

2. 상한만으로 말할 수 있는 것

어떤 알고리즘의 비용이 O(n²)이라는 사실만 알고 있을 때, 실제 비용이 반드시 n²에 비례해 늘어난다고 말할 수 있을까요?

3. 저울로 가짜 동전 30개 찾기

가짜 동전 하나가 더 가볍고, 결과가 세 가지인 저울을 쓸 수 있습니다. 후보가 30개라면 어떤 방법을 쓰더라도 최소 몇 번은 달아야 할까요?

다음 글 리스트·배열·문자열·딕셔너리의 역할에서는 자료를 어떤 구조에 담느냐에 따라 같은 작업의 비용이 어떻게 달라지는지 봅니다. 같은 입력으로 증가율과 실제 측정을 나란히 비교하는 일은 정렬의 정답 조건·안정성·시간 측정에서, 입력의 길이가 둘이라서 n 하나로 합칠 수 없는 경우는 LCS에서 다룹니다.