Quick Select

선택문제

• n개의 값 중에서 k번째로 작은수 찾기
  • Quick Select
  • Medium Of Mediums

1. P를 고른다: pivot, random
2. A={p보다 작은 값}
   B={p보다 큰 값}
   M={P와 같은 값}
3. if|A| > k : k번째로 작은 수는 A에 있다(재귀 사용)
   A에서 k번째 작은 값이 전체에서 k번째 작은 값이다 -> M과 B에는 없다
   elif |A|+|M|< K: B에서 찾는다
   B에서 k-|A|+|M|번째
   else: #M에 있다
   return P

최악의 경우

• T(n) = T(n-1)+n
  n번을 비교하는데 수를 n-1개씩 줄이면서 확인
  O(n^2)이다

최선의 경우

• T(n) = T(n/2)+n
  n=2^k라 한다면 (T(2/n^2)+2/n)+n
  O(n) <=2n