364
2014-03-16 03:40:51
0
제가 아직 잘 몰라 질문자님 의도를 파악하지 못했는데 엔델님 링크를 보고 많은 공부를 할 수 있었습니다. 감사합니다 ^^
먼저 질문자님께서 찾으시는 부분은 Quick Selection 으로 수수숭님께서 언급하셨던 것처럼 Quick Sorting의 특징을 이용한 Selection Algorithm 입니다.
이 알고리즘은 Quick Sort 처럼 동작하며 별다른 재귀호출 없이 구현할 수 있습니다.
Quick Selection 동작 시간을 T(QS) 이라고 하면 Quick Sort 처럼 항상 절반씩 나누기 때문에
T(QS) = N + N/2 + N/4 + ... 의 시간이 걸리게 되고
T(QS/2) = N/2 + N/4 + ... 를 이용하여
T(QS) - T(QS/2) = N
T(QS) = 2N 의 결론을 내릴 수 있습니다. ( = O(N) )
Quick Sort와의 차이점은 상위 K 번째만을 선택한다는 의미에서 Partition이 될때 K가 속한 Partition만 신경을 쓰게 됨으로써, 속도 향상이 있습니다.
Heap Sorting 의 경우, Tree를 구성하는데 log K 이를 반복하는데 N이 걸려 N log K 가 되고 K가 작다면 N에 가까워 지긴 하지만 링크를 따라가 다른 분이 실험하신 내용을 보니 Quick Selection이 Heap 보다도 더 빠른 성능을 보인다고 합니다.