알고리즘(7) - 선택 알고리즘 Selection algorithm

선택 알고리즘 Selection algorithm

---

눈 앞에서 각각 숫자가 놓여 있다. 1, 3, 5, 6, 7 ... 여기서 만약 3번째로 큰 원소를 찾아야 한다. 여기서 보통 O(n log n) 시간이 걸리는 정렬 알고리즘을 사용하여 정렬해놓고 위치를 찾을 수 있다.

 

하지만, 더 빠르게 찾을 수도 있다. 더욱 n에 비례하는 시간에 근접할 수 있는 알고리즘이 선택 알고리즘 selection algorithm이다.

 

선택 알고리즘에는 두 가지 유형이 있다.

• 평균적으로 선형시간(n에 비례한 시간)이 소요되는 선택 알고리즘을 말한다. (select라 보통 표현한다.)
• '최악'의 경우에도 선형시간이 보장되는 선택 알고리즘이다. (linearselect라 보통 표현한다.)

여기서는 일반적인 선택 알고리즘을 먼저 설명하겠다.

 

 

선택 알고리즘

---

 

 

위에 있는 무작위한 배열이 있다고 가정해보자. 또 선택 알고리즘을 사용하여 n번째로 작은 원소를 찾고 싶다고 가정한다.

 

여기서 정렬을 하진 않더라도 n개의 원소를 각각 적어도 한 번씩을 봐야 한다. 따라서 Ω(n)의 시간이 걸린다.

 

 선택 알고리즘을 간단히 코드로 표현하자면 다음과 같다.

 

코드 구현

 

 이 코드의 구현 원리는 사진으로 보면 다음과 같다.

 

2번째로 작은 원소를 찾는다고 한다. partition 메소드로 기준값을 갖고 분할을 한다. 성공적으로 마쳤을 때는 기준값보다 큰 원소는 오른쪽으로, 작은 원소는 왼쪽으로 가게 된다. 여기서 2번째 작은 원소를 찾으려면 왼쪽 범위로 다시 분할하여 찾는다.

 

평균적 선택 알고리즘의 수행시간

 

이번에는 수행시간을 보자. 

if (i < k) then return select(A, p, q-1, i) ; -> T(n/2)
else if (i = k) then return A[q] ;
else return select(A, q+1, r, i-k) ; -> T(n/2)

구현된 코드에서 Θ(n)의 시간을 갖는 partition 메소드를 제외하면, 재귀적 함수 시간을 if문의 select 메소드는 각각 T(n/2)의 시간을 갖는다. 이를 마스터정리로 풀어보면 h(n)으로 풀 수 있다. 허나 f(n)이 h(n)보다 크므로 T(n) = Θ(n)이 된다.

 

최악의 경우 선택 알고리즘

---

quick sort의 최악의 경우는 한쪽으로 치우쳐져 분할되는 경우다. 이는 선택알고리즘에서도 마찬가지다. 이때는 선택 알고리즘이라 할지라도 Θ(n^2)의 시간이 할애된다.

 

linearSelect는 최악의 경우에도 분할 균형을 어느 정도 보장되도록 함으로써 수행시간이 평균에 맞출 수 있도록 한다.

 

 

기준원소를 중심으로 한 대소관계를 다음과 같은 그림으로 보일 수 있다.

 

 

즉, 주어진 배열을 분할하고 그 분할된 배열에서 중앙값을 뽑고, 다시 그 중앙값들의 배열에서 다시 중앙값을 뽑는 재귀적 과정을 갖는다. 이 과정을 통해 하나만 남은 값은 기준원소가 되어 다시 분할을 진행할 수 있다. 그렇게 한다면 분할의 균형을 일정 비율 이상 나빠지지 않도록 관리하는 것이 가능하다.

 

이렇게 했을 시, 최악의 경우에도 Θ(n)의 수행시간을 갖는다.