[알고리즘] 선형 시간 선택 알고리즘

어떤 시간에서든 선형 시간에 가능하도록 보장해줄 수 있도록 하는 알고리즘이 없을까? 이를 가능하도록 하는 알고리즘이 선형 시간 선택 알고리즘이다.

🚩평균 선형 시간 선택 알고리즘

선택 알고리즘은 퀵 정렬에서 사용했던 분할 알고리즘을 사용한다. 위의 경우에서 분할 알고리즘을 사용한다면 i번째 값을 찾을 수 있다. 기준원소를 5로 하고, 3번째로 작은 원소를 찾는다고 해보자. 분할 알고리즘을 통해 5는 5번째 수 임을 알 수 있다.


=> arr배열에서 5를 기준으로 분할 한 결과


5가 5번째로 작은 원소이므로, 3번째로 작은 원소는 5의 왼쪽에 위치한다. 5의 왼쪽에 있으므로 오른쪽 부분은 볼 필요가 없어졌다. 이제 왼쪽에서 3번째로 작은 원소를 찾아야 한다. 이번에는 2를 기준으로 분할한다. 이때, 오른쪽은 더 이상 분할을 할 필요가 없다.

=>2를 기준으로 분할 한 결과

2는 2번째로 작은 원소임을 알았다. 3번째로 작은 원소는 이제 2의 오른쪽 부분에서 1번째로 작은 원소일 것이다. 이 과정을 반복하며 값을 찾아내면 3이라는 원소가 나온다. 따라서 평균 선형 시간 선택 알고리즘은 기준원소를 통해 그룹을 분할을 하고, 두 그룹중 하나만을 선택해서 문제의 크기를 적절히 줄여나가 O(n)시간만에 i번째 원소를 선택할 수 있다.

또, 분할의 균형이 맞지 않고 찾고자 하는 원소가 운 나쁘게도 큰 그룹에 속하는 일이 반복되면 성능을 보장하지 못한다.

=>평균 선형 시간 선택 알고리즘이 퀵정렬과 유사한데, 퀵정렬은 모든 원소를 정렬하는 것이 목적이고, 평균 선형 시간 선택 알고리즘은 i번째 작은 원소 선택만 하면 끝이다.

그럼 최악의 경우에는 ?

만약에 분할 할 때 마다 그룹이 항상 1:n-1개의 원소로 분할 되고, 심지어 선택하는 그룹이 항상 n-1개 원소를 가진 그룹이면 어떨까?

이런 상황에서는 그룹을 나누고 선택해서 문제의 크기를 획기적으로 줄여나갔다고 할 수 있을까?

이러한 최악의 경우에는 이 알고리즘도 Θ(n^2)의 시간이 걸리게 될 것이다. 이것이 위 알고리즘이 "평균"선형 시간 선택 알고리즘인 이유인듯 하다.

최악의 경우에도 선형시간을 보장하는 선택 알고리즘
위에서 그룹이 항상 1:n-1개의 원소로 분할되고 계속해서 찾고자 하는 원소가 큰 그룹에 속하는 일이 반복되면 Θ(n^2)시간이 걸린다고 했다.

그렇다면 계속해서 일정 비율 이상은 보장받도록 하면 어떨까?
아무리 나쁜 경우여도 "이 비율"이상은 유지되도록 말이다.

즉, 분할의 균형이 나빠보여도 일정한 상수비만 넘지 않으면 점근적 복잡도는 항상 Θ(n)이 된다. 여기에 더하여 균형을 맞추는 오버헤드가 너무 커져버리면 목표를 이룰 수 없다.

여기서 왼쪽 상단, 오른쪽 하단의 M보다 큰/작음이 확실한 원소들의 존재로 인해 분할 할 때 양쪽 그룹의 비율이 일정 수준 이상으로 보장된다.

오버헤드를 포함해도 Θ(n)시간이 걸림을 증명할 수 있다.