# 내가 좋아하는 알고리듬: Linear Time Median Finding (2018)

> Clean Markdown view of GeekNews topic #16032. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=16032](https://news.hada.io/topic?id=16032)
- GeekNews Markdown: [https://news.hada.io/topic/16032.md](https://news.hada.io/topic/16032.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-07-26T21:33:20+09:00
- Updated: 2024-07-26T21:33:20+09:00
- Original source: [rcoh.me](https://rcoh.me/posts/linear-time-median-finding/)
- Points: 2
- Comments: 1

## Topic Body

##### O(n log n)에서 중간값 찾기  
  
- 리스트를 정렬한 후 중간값을 선택하는 가장 간단한 방법  
- 비교 기반 정렬의 시간 복잡도는 `O(n log n)`임  
- 코드 예시:  
  ```python  
  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가 개발한 재귀적 알고리듬  
- 과정:  
  1. 리스트에서 임의의 인덱스를 선택하여 **피벗**으로 설정  
  2. 피벗을 기준으로 리스트를 두 그룹으로 나눔:  
     - 피벗보다 작거나 같은 요소들  
     - 피벗보다 큰 요소들  
  3. 중간값이 포함된 그룹을 재귀적으로 탐색  
  
- 코드 예시:  
  ```python  
  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" 알고리듬을 사용하여 피벗을 선택  
- 과정:  
  1. 리스트를 5개씩 그룹으로 나눔  
  2. 각 그룹을 정렬하고 중간값을 선택  
  3. 중간값들의 중간값을 피벗으로 선택  
  
- 코드 예시:  
  ```python  
  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++ 표준 라이브러리에서 사용됨

## Comments



### Comment 27588

- Author: neo
- Created: 2024-07-26T21:33:20+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=41066536)   
- 4년 전 다양한 중위수 알고리듬을 비교한 긴 글을 작성했음  
- 10-15년 전, 수십억 개의 값을 가진 로그 항목에서 중위수를 찾기 위해 MapReduce를 사용했음  
  - 데이터의 정밀도와 범위를 알면 버킷 정렬을 사용할 수 있었음  
  - 타이밍을 정수 밀리초로 표현하고 히스토그램을 생성하여 중위수를 쉽게 찾을 수 있었음  
- 2017년에 중위수-중위수 접근법을 다른 선택 알고리듬과 경쟁력 있게 만든 논문이 발표되었음  
  - Andrei Alexandrescu가 이 알고리듬에 대해 2016년에 강연을 했음  
- 중위수-중위수 알고리듬의 저자 목록이 매우 유명함  
  - Manuel Blum, Robert Floyd, Ron Rivest, Bob Tarjan, Vaughan Pratt 등  
- Floyd-Rivest 알고리듬도 효율적이지만 이해하기 어려움  
- 스트리밍 알고리듬을 사용하면 전체 데이터를 메모리에 저장하지 않고도 근사치를 계산할 수 있음  
- 퀵소트를 수정하여 중위수를 선택하는 방법이 있음  
- 인터뷰 질문으로 수조 개의 숫자가 있는 리스트에서 중위수를 찾는 문제를 받았음  
  - 상한과 하한을 설정하여 중위수를 찾는 방식을 사용했지만 최적의 방법은 아니었음  
  - 우선순위 힙을 사용하는 더 효율적인 방법이 있었음  
  - 이후 LeetCode 구독을 시작했음  
- Go로 구현된 간단한 예제를 공유했음  
- Radix 정렬은 정수 외에도 문자열 등 다양한 데이터 타입에 사용할 수 있음