O(n log n)에서 중간값 찾기
- 리스트를 정렬한 후 중간값을 선택하는 가장 간단한 방법
- 비교 기반 정렬의 시간 복잡도는
O(n log n)임 - 코드 예시:
def nlogn_median(l): l = sorted(l) if len(l) % 2 == 1: return l[len(l) // 2] else: return 0.5 * (l[len(l) // 2 - 1] + l[len(l) // 2])
평균 O(n)에서 중간값 찾기
-
"quickselect" 알고리듬을 사용하여 평균적으로 선형 시간에 중간값을 찾을 수 있음
-
Tony Hoare가 개발한 재귀적 알고리듬
-
과정:
- 리스트에서 임의의 인덱스를 선택하여 피벗으로 설정
- 피벗을 기준으로 리스트를 두 그룹으로 나눔:
- 피벗보다 작거나 같은 요소들
- 피벗보다 큰 요소들
- 중간값이 포함된 그룹을 재귀적으로 탐색
-
코드 예시:
import random def quickselect_median(l, pivot_fn=random.choice): if len(l) % 2 == 1: return quickselect(l, len(l) // 2, pivot_fn) else: return 0.5 * (quickselect(l, len(l) // 2 - 1, pivot_fn) + quickselect(l, len(l) // 2, pivot_fn)) def quickselect(l, k, pivot_fn): if len(l) == 1: assert k == 0 return l[0] pivot = pivot_fn(l) lows = [el for el in l if el < pivot] highs = [el for el in l if el > pivot] pivots = [el for el in l if el == pivot] if k < len(lows): return quickselect(lows, k, pivot_fn) elif k < len(lows) + len(pivots): return pivots[0] else: return quickselect(highs, k - len(lows) - len(pivots), pivot_fn)
평균 O(n) 증명
- 피벗이 리스트를 대략 절반으로 나누는 경우, 각 재귀 호출은 이전 단계 데이터의 절반에서 작동함
- 수학적 증명:
C = n + n/2 + n/4 + n/8 + ... = 2n = O(n)
결정적 O(n)
-
최악의 경우에도 선형 시간 보장
-
"median-of-medians" 알고리듬을 사용하여 피벗을 선택
-
과정:
- 리스트를 5개씩 그룹으로 나눔
- 각 그룹을 정렬하고 중간값을 선택
- 중간값들의 중간값을 피벗으로 선택
-
코드 예시:
def pick_pivot(l): assert len(l) > 0 if len(l) < 5: return nlogn_median(l) chunks = chunked(l, 5) full_chunks = [chunk for chunk in chunks if len(chunk) == 5] sorted_groups = [sorted(chunk) for chunk in full_chunks] medians = [chunk[2] for chunk in sorted_groups] median_of_medians = quickselect_median(medians, pick_pivot) return median_of_medians def chunked(l, chunk_size): return [l[i:i + chunk_size] for i in range(0, len(l), chunk_size)]
요약
- quickselect 알고리듬은 적절한 피벗을 선택하면 선형 시간에 중간값을 찾을 수 있음
- median-of-medians 알고리듬은 최악의 경우에도 선형 시간을 보장하는 피벗 선택 방법
- 실제로는 임의의 피벗 선택이 충분히 효과적임
GN⁺의 정리
- 이 글은 중간값을 찾는 다양한 알고리듬을 설명하고, 특히 선형 시간에 중간값을 찾는 방법을 다룸
- quickselect 알고리듬은 평균적으로 빠르지만, 최악의 경우를 대비해 median-of-medians 알고리듬을 사용할 수 있음
- 실제 응용에서는 임의의 피벗 선택이 대부분 충분히 효과적임
- 비슷한 기능을 가진 알고리듬으로는 introselect가 있으며, 이는 C++ 표준 라이브러리에서 사용됨
Hacker News 의견
- 4년 전 다양한 중위수 알고리듬을 비교한 긴 글을 작성했음
- 10-15년 전, 수십억 개의 값을 가진 로그 항목에서 중위수를 찾기 위해 MapReduce를 사용했음
- 데이터의 정밀도와 범위를 알면 버킷 정렬을 사용할 수 있었음
- 타이밍을 정수 밀리초로 표현하고 히스토그램을 생성하여 중위수를 쉽게 찾을 수 있었음
- 2017년에 중위수-중위수 접근법을 다른 선택 알고리듬과 경쟁력 있게 만든 논문이 발표되었음
- Andrei Alexandrescu가 이 알고리듬에 대해 2016년에 강연을 했음
- 중위수-중위수 알고리듬의 저자 목록이 매우 유명함
- Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt 등
- Floyd-Rivest 알고리듬도 효율적이지만 이해하기 어려움
- 스트리밍 알고리듬을 사용하면 전체 데이터를 메모리에 저장하지 않고도 근사치를 계산할 수 있음
- 퀵소트를 수정하여 중위수를 선택하는 방법이 있음
- 인터뷰 질문으로 수조 개의 숫자가 있는 리스트에서 중위수를 찾는 문제를 받았음
- 상한과 하한을 설정하여 중위수를 찾는 방식을 사용했지만 최적의 방법은 아니었음
- 우선순위 힙을 사용하는 더 효율적인 방법이 있었음
- 이후 LeetCode 구독을 시작했음
- Go로 구현된 간단한 예제를 공유했음
- Radix 정렬은 정수 외에도 문자열 등 다양한 데이터 타입에 사용할 수 있음