복잡도: 점화식과 마스터 정리

분할 정복 알고리즘의 실행 시간은 점화식으로 나타냅니다. 한 호출의 비용은 재귀 호출들의 비용에 나누고 합치는 비용을 더한 값입니다. 이 장에서는 점화식을 푸는 방법을 익히고, 대표 알고리즘을 다른 방법과 비교합니다.

점화식 세우기

크기 n인 입력을 크기 n/b인 부분 문제 a개로 나누고, 나누고 합치는 데 f(n)을 쓴다면 T(n) = a * T(n/b) + f(n)입니다. 병합 정렬은 절반 크기 호출 두 번에 선형 시간 병합을 하므로 T(n) = 2T(n/2) + O(n)입니다.

합계를 보려면 재귀 트리를 그려 봅니다. 병합 정렬의 트리는 log2 n 단계이고 단계마다 작업량의 합이 n입니다.

단계 0:  n                          -> n
단계 1:  n/2  n/2                   -> n
단계 2:  n/4  n/4  n/4  n/4         -> n
...      (log2 n 단계)
합계:    n * log2 n = O(n log n)

마스터 정리

a >= 1, b > 1일 때 T(n) = a * T(n/b) + f(n)에서 c = log_b(a)를 임계 지수라고 합니다. 트리의 잎 개수가 n^c처럼 늘어나기 때문입니다. f(n)을 n^c와 비교합니다.

1. 어떤 d < c에 대해 f(n) = O(n^d)이면 잎이 지배합니다. T(n) = Θ(n^c)입니다.
2. 어떤 k >= 0에 대해 f(n) = Θ(n^c * (log n)^k)이면 모든 단계의 비용이 비슷합니다. T(n) = Θ(n^c * (log n)^(k+1))입니다.
3. 어떤 d > c에 대해 f(n) = Ω(n^d)이고, 어떤 상수 q < 1에 대해 a * f(n/b) <= q * f(n)이면 뿌리가 지배합니다. T(n) = Θ(f(n))입니다.

퀵셀렉트의 최악의 경우 T(n) = T(n - 1) + O(n) = O(n^2)은 마스터 정리로 풀 수 없습니다. 부분 문제가 일정한 비율이 아니라 원소 하나만큼 줄어들기 때문입니다.

카라추바: 곱셈 네 번 대신 세 번

두 수를 m자리에서 나눕니다. x = x1 * 10^m + x0, y = y1 * 10^m + y0이면 x * y = z2 * 10^(2m) + z1 * 10^m + z0이고, z2 = x1 * y1, z0 = x0 * y0, z1 = x1 * y0 + x0 * y1입니다. z1을 그대로 계산하면 곱셈이 두 번 더 필요해 4T(n/2), 곧 O(n^2)이 되어 손으로 하는 곱셈과 다를 바가 없습니다. 카라추바는 z1 = (x1 + x0) * (y1 + y0) - z2 - z0으로 곱셈을 한 번만 더 합니다. 부분 문제가 세 개이므로 O(n^log2(3)), 약 O(n^1.585)입니다.

def karatsuba(x, y):
    """음이 아닌 두 정수의 곱. 재귀 곱셈은 세 번만 한다."""
    if x < 10 or y < 10:
        return x * y
    m = max(len(str(x)), len(str(y))) // 2
    x1, x0 = divmod(x, 10 ** m)
    y1, y0 = divmod(y, 10 ** m)
    z2 = karatsuba(x1, y1)
    z0 = karatsuba(x0, y0)
    z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0
    return z2 * 10 ** (2 * m) + z1 * 10 ** m + z0

print(karatsuba(1234, 5678) == 1234 * 5678)  # True

최근접 점 쌍: 띠 확인이 싼 이유

점 n개 중 가장 가까운 두 점을 찾을 때는 점을 x좌표로 정렬하고, x좌표의 중앙값에서 나눈 뒤, 두 절반을 풀어 둘 중 더 작은 최소 거리 d를 얻습니다. 이보다 가까운 쌍은 반드시 나누는 선을 가로지르므로 두 점 모두 선을 중심으로 폭이 2d인 띠 안에 있습니다. 띠의 점을 y좌표 순으로 놓으면 각 점은 뒤따르는 점 몇 개(많아야 7개)와만 비교하면 됩니다. 서로 d 이상 떨어진 점은 d와 2d 크기의 상자에 그보다 많이 들어갈 수 없기 때문입니다. 병합 정렬처럼 두 절반을 y좌표 순으로 병합하면 합치기가 O(n)이므로 T(n) = 2T(n/2) + O(n) = O(n log n)입니다. 단계마다 띠를 새로 정렬하면 O(n log^2 n)이 됩니다.

작업량 직접 세어 보기

연산 횟수를 세어 보면 분석을 빠르게 확인할 수 있습니다.

def count_mults(e):
    """지수 e 에 대해 재귀 빠른 거듭제곱이 하는 곱셈 횟수."""
    if e == 0:
        return 0
    return count_mults(e // 2) + (2 if e % 2 else 1)

for e in (10, 1000, 10**6, 10**18):
    print(e, "naive:", max(e - 1, 0), "fast:", count_mults(e))

e = 10^18이면 단순한 방법은 곱셈이 약 10^18번 필요하지만 빠른 거듭제곱은 120번도 되지 않습니다.

다른 방법과 비교

공간도 따져야 합니다. 병합 정렬은 병합에 O(n) 추가 메모리가 필요하고, 균형 있게 나누면 재귀 깊이는 O(log n)입니다. 퀵셀렉트는 제자리에서 동작하지만 피벗이 나쁘면 재귀가 O(n) 깊이까지 내려갈 수 있습니다. 그래서 앞 장들처럼 반복문 형태로 쓰는 편이 Python에서는 안전합니다.

정리

• T(n) = a * T(n/b) + f(n)을 세우고 f(n)을 n^log_b(a)와 비교합니다.
• 단계마다 비용이 같으면 log n배가 붙고, 그렇지 않으면 잎이나 뿌리가 지배합니다.
• 카라추바는 부분 문제 네 개를 세 개로 줄여서 빨라집니다.
• 일정한 비율로 줄어드는 것이 중요합니다. 원소 하나씩 줄면 제곱 시간이 됩니다.