# Quickselect

• 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)임을 증명한다.