쉽게 배우는 알고리즘-05선택 알고리즘

1) i번 작은 수 찾기

-배열 A[p..r]에서 i번째 작은 원소를 찾는다

-선택 알고리즘의 수행 시간 범위

  Ω(n): n개의 원소 각각을 한 번씩 보아야 함

  O(nlogn): 정렬한 후 i 번째 원소를 고름

  ∴nlogn~n

 

-Quicksort 기반