# Selection

• 2026년 6월 29일 알고리즘
  추가 설명 — 왜 하필 5개로 나누는가

  median of medians가 그룹을 5개로 나누는 이유. 그룹 크기 g를 일반화해 두 부분문제 비율의 합이 1보다 작아야 선형임을 보인다. g=3과 g=4는 합이 정확히 1이라 깨지고, g=5는 0.9로 성립한다. g=7 이상은 수축이 좋아지는 대신 그룹 정렬 비용이 늘어 맞선다.

• 2026년 6월 29일 알고리즘
  추가 설명 — quickselect는 왜 평균 O(n)인가

  선택 문제 본문이 '대부분 O(n)'으로 넘어간 quickselect의 평균 시간을 기댓값 점화식으로 엄밀히 따진다. quick sort와 달리 한쪽으로만 재귀하기 때문에 E(n)에 max 항이 생기고, 이를 상계로 풀면 E(n) ≤ 4n = O(n)이다.

• 2026년 6월 29일 알고리즘
  선택 문제 — k번째 원소를 정렬 없이 O(n)에 찾기

  k번째로 작은 원소를 찾는 선택 문제. 정렬은 O(n log n)이지만 선택은 더 쉽다. quick sort의 분할을 재활용한 quickselect를 보고, 최악 O(n²)을 없애려 5개씩 묶는 median of medians로 최악에도 O(n)임을 증명한다.