MoM

---

Median of Medians (MoM)

• 퀵셀렉트 알고리즘 이용 → 최악의 경우를 방지하기 위해 랜덤 pivot말고 좀 똑똑하게 고르자 → approximate median으로 pivot 고름(대략적인 중앙값) → MoM이 pivot 이름 → 이를 통해 i번째 원소 찾기 가능
• 보다 밸런스 파티션을 보장함

 

-Select Procedure

1. 5개원소로 그룹 만듦 → [n/5]개의 그룹 탄생
2. 각 그룹을 정렬한 후 해당 그룹 별로 median(중앙값) 찾기 → 중간값들이 새 배열 형성
3. 새 배열인 median들 중에서 median 찾아서 pivot으로 삼음 (MoM 재귀적 호출 통해) ⇒ T([n/5])
4. 기존 배열을 pivot 기준으로 작은 값, 큰 값 두 구간으로 나눔 → 이때 pivot이 k번째 작은 값임을 알 수 있음
5. pivot인 k번째 원소를 통해 재귀적으로 i번째 원소 찾기 ⇒ T(3n/4)
   • i = k : 바로 찾음
   • i < k: 왼쪽 구간에서 다시 MoM 재귀 호출하여 찾아야 됨
   • i > k: 오른쪽 구간에서 다시 MoM 재귀 호출하여 찾아야 됨

더 큰 경우나 작은 경우 등, 최대 3/4 공간에서 다시 수행해야 되니 T(3n/4)

 

-재귀식

재귀식 = 재귀적으로 pivot을 이용해 i번째 원소 찾기 + 재귀적으로 median 중에서 median 찾기(MoM) + 각 그룹마다 삽입 정렬

 

-시간 복잡도

• T(n) = O(n)

 

-Experimental Result

• MoM이 pivot을 선택하는데에 있어서는 좋은 알고리즘임
• 그러나 현실 데이터에선 MoM을 결정하는 과정에서 오버헤드가 생겨서 느림
• 따라서 randomized quick select가 종종 MoM 성능을 넘어섬