▲

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

 (rcoh.me)
2P by neo 4달전 | favorite | 댓글 1개

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가 개발한 재귀적 알고리듬

  • 과정:

    1. 리스트에서 임의의 인덱스를 선택하여 피벗으로 설정
    2. 피벗을 기준으로 리스트를 두 그룹으로 나눔:
      • 피벗보다 작거나 같은 요소들
      • 피벗보다 큰 요소들
    3. 중간값이 포함된 그룹을 재귀적으로 탐색

  • 코드 예시:

    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. 중간값들의 중간값을 피벗으로 선택

  • 코드 예시:

    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++ 표준 라이브러리에서 사용됨
▲
neo 4달전  [-]
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 정렬은 정수 외에도 문자열 등 다양한 데이터 타입에 사용할 수 있음
답변달기