최악의 경우에도 선형 시간을 보장하는 선택 알고리즘

분할의 균형이 맞지 않게 분할이 된 상태에서 찾고자 하는 원소가 큰 그룹에 들어가는 일이 반복되면 성능이 선형을 넘어서게 된다.

반면 일정한 상수비를 지켜서 계속 분할이 된다면 복잡도는 항상 O(n)이 된다.

즉, 99:1로 분할이 계속 되어도 최악의 경우에도 O(n)을 만족한다는 것이다.

T(n) = T(99n/100) + O(n)

 

 

최악의 경우 선형 시간 선택 알고리즘

알고리즘 상황 설명

알고리즘의 대략적인 방법은 다음과 같다.

0. 전체 원소가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다.

1. 전체 원소를 5개씩의 원소를 가진 그룹들로 나눈다.(이때 꼭 5개일 필요는 없다)

2. 각 그룹에서 중앙값을 찾는다. -> 상수시간 * O(n/5) = O(n)

3. 중앙값들의 중앙값을 구한다. 이때 구하는 방법은 이 알고리즘을 자가 호출하여 구한다. 짝수이면 두 중앙값 중 임의로 선택한다. -> T(ceil(n/5))

4. 이렇게 구한 M을 기준원소로 삼아 전체 원소를 분할한다.(M보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에)

5. 분할된 그룹 중 적절한 그룹을 선택하여 재귀적으로 반복한다. -> 최악의 경우에도 T(7n/10 + 2)

 

 

5번에 대해서 좀 더 설명을 하자면 아주 최악의 경우에도 M이상인 원소들의 개수는 3n/10 - 2개이다.(그림에서 M과 초록색으로 칠한 부분들)

이때의 분할 비율은 7n/10+2 : 3n/10 -2이므로 대강 7:3과 비슷하다.

 

 

 

따라서 알고리즘의 점화식은 다음과 같다.

T(n) ≤ T(ceil(n/5)) + T(7n/10+2) + O(n)

 ≤T(n/5+1) + T(7n/10+2) + O(n)

  

이때 T(k) ≤ ck라 가정하고 귀납법을 하면

T(n)≤ cn을 유도할 수 있다.

 

 

 

 

 

출처 : 서울대학교 컴퓨터공학부 문병로 교수님 알고리즘 수업