# Linear Time

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

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