· 개발

중앙값의 중앙값(BFPRT): 최악의 경우에도 선형 시간에 k번째 값 찾기

1973년 Blum·Floyd·Pratt·Rivest·Tarjan 논문의 PICK 알고리즘이 최악의 경우에도 선형 시간에 k번째 값을 찾는 원리와, 묶음 크기 5가 어디서 나오는지 원 논문 기준으로 정리합니다.

algorithmsselectionmedian-of-medianscomplexity

n개의 값 중 k번째로 작은 값을 구하는 문제를 선택(selection) 문제라고 합니다. 중앙값이 대표적인 예입니다. 전부 정렬한 뒤 k번째를 꺼내면 답은 나오지만, 값 하나를 얻으려고 전체 순서를 다 정하는 셈입니다.

Blum, Floyd, Pratt, Rivest, Tarjan은 1973년 논문 “Time Bounds for Selection”에서 k가 무엇이든 비교 횟수가 n에 대한 선형 함수를 넘지 않는 알고리즘 PICK을 제시했습니다. 피벗을 고르는 방식 때문에 흔히 “중앙값의 중앙값(median of medians)“이라고 부르고, 저자들의 머리글자를 따서 BFPRT라고도 합니다. 이 글은 이 논문(Journal of Computer and System Sciences 7권, 448–461쪽, 저자 Rivest가 공개한 사본)을 기준으로 PICK의 구조, 선형이 되는 이유, 그리고 “왜 5개씩 묶는가”라는 질문을 다룹니다. 이후의 개선 연구나 특정 언어 라이브러리의 구현은 다루지 않습니다.

피벗 하나가 성능을 정한다

k번째 값을 찾는 가장 직관적인 방법은 퀵소트의 분할을 응용하는 것입니다. 피벗 m을 하나 골라 나머지 값과 모두 비교하고, k번째 값이 있을 수 없는 쪽을 버린 뒤 남은 쪽에서 반복합니다. 논문은 PICK이 Hoare의 FIND 알고리즘과 매우 비슷하며, 분할 기준 m을 더 신중하게 고른다는 점만 다르다고 설명합니다.

이 방식의 약점은 피벗에 있습니다. 다음은 이 글의 계산입니다. 피벗이 매번 남은 값 중 최솟값이나 최댓값이라면 한 번 분할할 때마다 값이 하나씩만 줄어듭니다. 그러면 비교 횟수는 대략 n + (n − 1) + … 이 되어 n²/2 정도까지 늘어납니다. 퀵소트에서 피벗 선택이 최악의 경우를 만드는 과정은 퀵소트의 최악의 경우 글에서 다뤘습니다. PICK은 피벗을 고르는 데 비교를 더 써서, 분할할 때마다 정해진 비율 이상을 버리도록 보장합니다.

PICK의 단계

논문은 PICK을 세 매개변수 c, d, b로 일반화해 설명합니다. 집합 S에서 i번째로 작은 값을 찾는다고 할 때 한 번의 반복은 다음과 같습니다.

  1. S를 길이 c인 열 n/c개로 나누고 각 열을 정렬합니다. 각 열에서 d번째로 작은 값을 모은 집합을 T라고 하고, T에서 b번째 값을 PICK으로 재귀 호출해 구해 m으로 삼습니다.
  2. 아직 대소 관계를 모르는 원소를 모두 m과 비교해 S에서 m의 순위를 구합니다.
  3. 순위가 i이면 m이 답이므로 멈춥니다. 순위가 i보다 크면 m 이상인 원소를, 작으면 m 이하인 원소를 버리고(이때 i도 버린 개수만큼 줄입니다) 1단계로 돌아갑니다.

d를 열의 가운데 위치로, b를 T의 가운데 위치로 잡으면 m은 “각 열 중앙값들의 중앙값”이 됩니다. 이름이 여기서 나왔습니다. 논문은 이렇게 버리는 부분집합이 매번 남은 원소의 4분의 1 이상을 포함한다고 말합니다.

선형이 되는 이유

논문은 최대 비교 횟수를 P(n)으로 두고, c = 21, d = 11, b = n/42를 골라 다음 점화식을 세웁니다(식 6).

P(n) ≤ 66n/21 + P(n/21) + n + P(31n/42)

각 항의 의미는 이렇습니다. 66은 Ford–Johnson 방법으로 21개를 정렬하는 비교 횟수 h(21)이므로, 첫 항은 열 n/21개를 모두 정렬하는 비용입니다. P(n/21)은 열 중앙값 n/21개에서 중앙값을 재귀로 찾는 비용, n은 m과 나머지 원소를 비교하는 비용의 상한, 마지막 P(31n/42)는 버리고 남은 원소에 대한 다음 반복입니다. 논문은 이로부터 귀납법으로 P(n) ≤ 58n/3을 얻습니다.

31n/42가 어디서 나오는지는 논문 그림 1에서 읽을 수 있습니다. 아래는 그 그림을 바탕으로 한 이 글의 계산이며, 열이 딱 나누어떨어지지 않는 경우와 ±1 차이는 무시했습니다(논문도 n이 c로 나누어떨어지지 않는 경우의 세부 사항은 생략한다고 밝힙니다). 열 중앙값의 절반, 즉 n/42개 열은 중앙값이 m 이하입니다. 정렬된 열이므로 이 열들에서는 아래쪽 11개가 모두 m 이하이고, 따라서 m 이하라고 확실히 아는 원소가 11n/42개 이상입니다. m 이상인 쪽도 같은 이유로 11n/42개 이상입니다. 어느 쪽을 버리든 11n/42개 이상이 사라지므로 남는 원소는 많아야 31n/42개입니다.

선형 시간이 나오는 핵심은 두 재귀 호출의 크기를 더한 값입니다. n/21 + 31n/42 = 33n/42로 n보다 작습니다. 다음 단계에서 다루는 원소 수의 합이 매번 일정 비율로 줄어들므로, 모든 단계의 비용을 더하면 수렴하는 등비급수가 되고 전체가 n에 비례합니다. 이 부분은 이 글의 설명이고, 논문은 같은 내용을 “매 단계 S의 상당한 비율을 버리고, 그 비용이 버린 원소 수에 비례하기 때문”이라고 요약합니다.

5개씩 묶는다는 숫자는 어디서 오나

중앙값의 중앙값을 “5개씩 묶는다”로 배웠다면, 원 논문의 숫자는 조금 의외일 수 있습니다. 기본 증명은 21개짜리 열을 쓰고, 상수를 줄인 개선판 PICK1은 15개짜리 열을 씁니다. 5라는 숫자는 증명 끝의 한 문장에만 나옵니다. “PICK이 선형 시간에 동작하려면 c ≥ 5여야 한다는 점에 주의하라.” 논문은 이 문장에 별도의 증명을 붙이지 않았습니다.

이유는 앞 절의 계산을 c에 대해 일반화하면 보입니다. 다음도 이 글의 계산입니다. 가운데 원소가 하나로 정해지도록 c를 홀수 2k + 1로 두면, m 이하라고 확실히 아는 원소는 열 절반에서 각각 k + 1개씩이므로 약 (k + 1)n/(2c)개이고, 남는 원소는 많아야 n − (k + 1)n/(2c)개입니다. 두 재귀 호출 크기의 합을 n에 대한 비율로 쓰면 다음과 같습니다.

열 크기 c 중앙값 재귀 다음 반복 합
3 1/3 2/3 1
5 1/5 7/10 9/10
7 1/7 5/7 6/7
21 1/21 31/42 11/14

c = 3이면 합이 정확히 1이라서 단계를 내려가도 다룰 원소 수의 합이 줄지 않고, 앞 절의 등비급수 논리로는 선형 상한이 나오지 않습니다. 5는 합이 1보다 작아지는 가장 작은 홀수이고, 5개씩 묶는 설명은 이 최소값을 쓰는 셈입니다. 다만 이 표는 PICK의 구조를 그대로 둔 단순한 상한 계산이고, 구조를 바꾼 다른 변형까지 판정하지는 않습니다.

반대로 c를 마음대로 키울 수도 없습니다. 1단계의 열 정렬 비용은 n·h(c)/c이고, 논문은 PICK이 선형이려면 c가 상수로 제한되어야 한다고 적습니다. 논문이 기본 증명에서 c = 21을 고른 것도 점화식 (5)의 상한을 최소화하기 위해서였습니다. 같은 점화식에 c = 5를 넣어 보면(5개 정렬에 비교 7번, 다음 반복 7n/10) 상한은 24n이 되어, c = 21일 때의 58n/3보다 큽니다. 이 비교는 이 글의 계산입니다. 5는 성립하는 최소값이고, 상수를 줄이는 데 가장 좋은 값은 아닙니다.

논문이 제시한 상수와 한계

논문의 결론은 선택을 최악의 경우에도 선형 시간에 할 수 있다는 것입니다. 개선판 PICK1으로는 어떤 i에 대해서도 비교 횟수가 약 5.43n을 넘지 않는다고 증명했고(정확히는 5.4305n이며 마지막 5가 순환), i가 양 끝에 가까울 때는 PICK2로 더 좋은 상한을 얻습니다. 하한 쪽으로는 중앙값을 구하려면 최소 3n/2 − 2번의 비교가 필요하다는 것을 보였습니다.

실용 면에서는 논문 스스로 단서를 달았습니다. PICK1은 부수적인 처리가 너무 많아서(원문은 “full of red tape”) 실제로 효율적으로 구현할 수는 없다고 적었고, 위아래 상한의 상수 모두 크게 개선될 수 있을 것이라고 봤습니다. 논문의 분석 대상은 비교 횟수이고, 입력은 서로 다른 n개의 수로 가정합니다.

Python으로 옮긴 예

아래 코드는 5개씩 묶는 PICK을 Python으로 옮긴 것입니다. 논문은 서로 다른 값을 가정하지만, 이 코드는 피벗과 같은 값을 따로 세어 중복 값도 처리합니다. k는 0부터 셉니다.

def select(a, k):
    """a에서 k번째(0부터 셈)로 작은 값을 반환한다."""
    if len(a) <= 5:
        return sorted(a)[k]
    # 5개씩 묶어 각 묶음의 중앙값을 모은다 (마지막 묶음은 더 짧을 수 있다)
    groups = [sorted(a[i:i + 5]) for i in range(0, len(a), 5)]
    medians = [g[len(g) // 2] for g in groups]
    # 중앙값들의 중앙값을 재귀로 구해 피벗으로 쓴다
    pivot = select(medians, len(medians) // 2)
    lo = [x for x in a if x < pivot]
    hi = [x for x in a if x > pivot]
    n_eq = len(a) - len(lo) - len(hi)
    if k < len(lo):
        return select(lo, k)
    if k < len(lo) + n_eq:
        return pivot
    return select(hi, k - len(lo) - n_eq)


print(select([9, 1, 8, 2, 7, 3, 6, 4, 5, 0, 5], 5))  # 5

이 코드는 구조를 보이기 위한 것입니다. 매 단계 새 리스트를 만들고, 피벗과의 비교도 논문처럼 이미 아는 관계를 건너뛰지 않습니다. 비교 횟수의 상수는 논문의 분석과 다르지만, 재귀 두 번의 크기 합이 n보다 작아지는 구조는 같습니다.

정리할 때 확인할 것

  • 보장의 종류: PICK의 선형 상한은 확률이나 평균이 아니라 최악의 경우에 대한 결정적 보장입니다.
  • 묶음 크기: 원 논문은 5를 고정하지 않습니다. 5는 이 구조에서 선형 논증이 성립하는 최소 홀수이고, 논문의 기본 증명은 21, 개선판은 15를 씁니다.
  • 상수: 논문이 증명한 상한은 약 5.43n번의 비교이고, 저자들도 이 상수가 개선될 여지가 크다고 봤습니다.
  • 중복 값: 논문은 서로 다른 값을 가정합니다. 구현할 때는 피벗과 같은 값을 따로 처리해야 합니다.

블로그로