선택 알고리즘

n개의 원소로 이루어진 집합에서 최소/최대 원소를 찾기 위해서는 선형시간 O(n)이 필요하다 적어도 모든원소를 한번씩은 봐야하는 것이다. 그렇다면 최소(혹은 최대) 원소가 아닌 2번째로 작은(혹은 큰) 원소를 찾기 위해서는 최소(최대)원소를 구하는 기본 과정에 2번째로 작은 원소를 저장하고 이를 갱신하는 과정을 추가 하면 된다. 위 과정은 최소/최대 원소를 구하는 과정보다 시간이 더 걸리긴 하지만 마찬가지로 선형시간내에 구할 수 있다. 하지만 n개의 원소로 이루어진 집합에서 중앙값을 구한다고 하면 위 과정에서 n/2번째 원소까지를 저장하며 갱신해야 하므로 이런 경우에는 O(n^2)의 시간이 걸리게 된다. 이런 경우에는 위와같은 방법을 사용하기보단 O(nlogn)시간이 소요되는 정렬 알고리즘을 통해 배열을..