[알고리즘] 선형 시간 선택 알고리즘
10개의 원소를 갖는 아래와 같은 배열이 있다. 이 배열에서 i번째의 값을 찾는다고 해보자. arr[10] = { 10, 2, 5, 7, 6, 4, 8, 1, 9, 3 } 우선 배열을 한 번씩은 다 훑어봐야 하므로 적어도 n에 비례하는 시간이, 즉 \(\Omega(n)\)이 될것이다. 정렬을 한다면 \(O(nlogn)\)일 것이다. 어떤 시간에서든 선형 시간에 가능하도록 보장해줄 수 있도록 하는 알고리즘이 없을까? 이를 가능하도록 하는 알고리즘이 바로 선형 시간 선택 알고리즘이다. 평균 선형 시간 선택 알고리즘 선택 알고리즘은 퀵 정렬에서 사용했던 분할 알고리즘을 사용한다. 위의 경우에서 분할 알고리즘을 사용한다면 i번째 값을 찾을 수 있다. 기준원소를 5로 하고, 3번째로 작은 원소를 찾는다고 해보자...