2024.10.10

[알고리즘] Linear-time selection

1. 선형 시간 선택 알고리즘 (Linear-Time Selection)

선형 시간 선택 알고리즘은 정렬되지 않은 데이터에서 원하는 순서의 요소(예: k번째로 작은 요소)를 선형 시간 내에 찾는 알고리즘이다. 일반적으로 정렬 알고리즘을 사용하여 데이터를 정렬한 후 원하는 요소를 찾을 수 있지만, 이는 보통 $O(n log n)$ 의 시간 복잡도를 갖는다. 그러나 선형 시간 선택 알고리즘은 정렬되지 않은 상태에서 $O(n)$ 의 시간 복잡도로 원하는 요소를 찾을 수 있다.

1-1. 아이디어 분석

이 알고리즘은 퀵 정렬(Quick Sort)의 분할 방식을 활용한다. 주어진 배열에서 임의의 피벗(pivot)을 선택하고, 이 피벗을 기준으로 배열을 분할한다. 피벗보다 작은 요소들은 왼쪽 부분 배열에, 큰 요소들은 오른쪽 부분 배열에 위치시킨다. 이때 피벗의 정확한 위치(인덱스)를 알 수 있으며, 이를 통해 원하는 k번째 요소가 피벗의 위치와 비교하여 어느 부분 배열에 존재하는지 판단할 수 있다.

• 만약 피벗의 위치가 k와 같다면, 피벗이 바로 k번째로 작은 요소이다.
• 피벗의 위치가 k보다 크다면, 원하는 요소는 왼쪽 부분 배열에 있다.
• 피벗의 위치가 k보다 작다면, 원하는 요소는 오른쪽 부분 배열에 있으며, 이때는 새로운 k 값을 조정하여 탐색을 계속한다.

2. 구현 분석

int select(int *arr, int left, int right, int k) {
    if (k >= 0 && k < right - left + 1) {
        int n = right - left + 1;
        int pivot = arr[left + rand() % n];

        // 분할 과정
        int pivot_idx = partition(arr, left, right, pivot);

        // 피벗의 위치와 k 비교
        if (pivot_idx - left == k)
            return arr[pivot_idx];
        else if (pivot_idx - left > k)
            return select(arr, left, pivot_idx - 1, k);
        else
            return select(arr, pivot_idx + 1, right, k - (pivot_idx - left + 1));
    }
    return INT_MAX; // 오류 처리
}

2-1. 함수 select

int select(int *arr, int left, int right, int k)

이 함수는 배열 arr에서 left부터 right까지의 범위에서 k번째로 작은 요소를 찾는 함수이다.

• 매개변수:

  • arr: 대상 배열
  • left: 탐색 범위의 시작 인덱스
  • right: 탐색 범위의 끝 인덱스
  • k: 찾고자 하는 순서 (0-based index)

• 기본 조건 검사:

  • if (k >= 0 && k < right - left + 1)를 통해 k의 유효성을 확인한다.
  • k가 현재 배열 범위 내에 있는지 검사하여 그렇지 않으면 오류를 반환한다.

• 피벗 선택:

  • int n = right - left + 1;을 통해 현재 부분 배열의 크기를 계산한다.
  • int pivot = arr[left + rand() % n];을 사용하여 부분 배열 내에서 임의의 피벗을 선택한다.

• 분할 과정:

  • int pivot_idx = partition(arr, left, right, pivot);을 호출하여 배열을 피벗을 기준으로 분할하고, 피벗의 최종 위치를 얻는다.

• 재귀 호출 및 반환:

  • if (pivot_idx - left == k):
    • 피벗의 위치가 k와 같다면, arr[pivot_idx]가 k번째로 작은 요소이다.
  • else if (pivot_idx - left > k):
    • 피벗의 위치가 k보다 크다면, 왼쪽 부분 배열에서 다시 탐색한다.
  • else:
    • 피벗의 위치가 k보다 작다면, 오른쪽 부분 배열에서 새로운 k 값을 조정하여 탐색한다.

• 오류 처리:

  • 만약 k가 유효한 범위가 아니라면 INT_MAX를 반환하여 오류를 나타낸다.

2-2. 함수 partition

partition 함수는 퀵 정렬에서 사용하는 분할 함수로, 피벗을 기준으로 배열을 재배열한다. 코드 구현은 다음과 같다.

int partition(int *arr, int left, int right, int pivot) {
    while (left <= right) {
        while (arr[left] < pivot)
            left++;
        while (arr[right] > pivot)
            right--;
        if (left <= right) {
            swap(arr[left], arr[right]);
            left++;
            right--;
        }
    }
    return left - 1;
}

• 기능:

  • 피벗보다 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 이동시킨다.
  • 피벗의 최종 위치를 반환한다.

• 작동 원리:

  • 두 개의 인덱스 left와 right를 사용하여 배열의 양 끝에서부터 탐색한다.
  • arr[left] < pivot인 동안 left를 증가시킨다.
  • arr[right] > pivot인 동안 right를 감소시킨다.
  • 두 인덱스가 유효하면 두 요소를 교환하고, left와 right를 각각 이동시킨다.

3. 정확성 분석

선형 시간 선택 알고리즘은 퀵 정렬의 분할 방식을 활용하여 원하는 순서의 요소를 찾는다. 이제 수학적 귀납법을 통해 알고리즘의 정확성을 증명해보자.

3-1. 명제 설정

명제 P(n): 배열 크기가 n일 때, select 함수는 k번째로 작은 요소를 정확히 찾아낸다.

3-2. 귀납적 증명의 구성 요소

1. 기저 사례(Base Case): n = 1일 때, 명제가 참임을 보인다.
2. 귀납 가정(Inductive Hypothesis): 배열 크기가 n보다 작은 모든 경우에 대해 명제가 참이라고 가정한다.
3. 귀납 단계(Inductive Step): 배열 크기가 n인 경우에도 명제가 참임을 보인다.
4. 종료성(Termination): 알고리즘이 유한한 단계 내에 종료함을 보인다.

3-3. 귀납적 증명

기저 사례

• n = 1인 경우:
  • 배열에 요소가 하나뿐이므로, k = 0일 때 해당 요소를 반환한다.
  • select 함수는 즉시 해당 요소를 반환하므로 명제 P(1)은 참이다.

귀납 가정

• 배열 크기가 n보다 작은 경우, 즉 모든 m < n에 대해 명제 P(m)이 참이라고 가정한다.

귀납 단계

• 배열 크기가 n인 경우:

  1. 피벗 선택 및 분할:

     • 임의의 피벗을 선택하고, partition 함수를 통해 배열을 분할한다.
     • 분할 후 피벗의 위치 pivot_idx를 얻는다.

  2. 피벗의 위치와 k 비교:

     • pivot_idx - left == k인 경우, 피벗이 k번째로 작은 요소이므로 반환한다.
     • pivot_idx - left > k인 경우, 왼쪽 부분 배열에서 탐색한다.
     • pivot_idx - left < k인 경우, 오른쪽 부분 배열에서 새로운 k 값을 조정하여 탐색한다.

  3. 재귀 호출의 유효성:

     • 재귀 호출되는 배열의 크기는 항상 n보다 작다.
     • 귀납 가정에 의해, 재귀 호출은 올바른 결과를 반환한다.

  4. **따라서, 배열 크기가 n인 경우에도 select 함수는 정확한 결과를 반환한다.

종료성

• 알고리즘의 종료성:
  • 각 재귀 호출마다 배열의 크기가 감소한다.
  • 최악의 경우에도 배열의 크기가 1씩 줄어들어 결국 n = 1인 기저 사례에 도달한다.
  • 따라서 알고리즘은 유한한 단계 내에 종료한다.

결론

• 기저 사례와 귀납 단계를 통해 모든 자연수 n에 대해 명제 P(n)이 참임을 증명하였다.
• 따라서 select 알고리즘은 항상 k번째로 작은 요소를 정확히 찾아낸다.

4. 효율성 분석

선형 시간 선택 알고리즘의 시간 복잡도를 분석해보자.

4-1. 평균 시간 복잡도

• 평균적으로 알고리즘은 O(n)의 시간 복잡도를 갖는다.
  • 피벗이 배열을 균등하게 분할할 경우, 각 재귀 호출에서 처리해야 할 배열의 크기는 절반으로 줄어든다.
  • 따라서 다음과 같은 재귀 관계를 얻는다. $$ T(n) = T\left(\frac{n}{2}\right) + O(n) $$
  • 이를 풀면 $T(n) = O(n)$이 된다.

4-2. 최악 시간 복잡도

• 최악의 경우, 알고리즘의 시간 복잡도는 O(n^2)이다.
  • 피벗이 배열을 극단적으로 불균형하게 분할할 경우, 예를 들어 항상 가장 큰 또는 가장 작은 값을 피벗으로 선택하면, 각 재귀 호출에서 배열의 크기가 1씩만 줄어든다.
  • 이때 재귀 호출의 깊이는 n이 되고, 전체 시간 복잡도는 다음과 같다. $$ T(n) = T(n - 1) + O(n) $$
  • 이를 풀면 $T(n) = O(n^2)$이 된다.

4-3. 최선 시간 복잡도

• 최선의 경우에도 평균 시간 복잡도와 동일하게 O(n)이다.

4-4. 개선 방안

• 무작위 피벗 선택:

  • 피벗을 무작위로 선택함으로써 평균적으로 균형 잡힌 분할을 기대할 수 있다.
  • 이는 최악의 경우를 발생시킬 확률을 낮춘다.

• Median of Medians 알고리즘:

  • 항상 좋은 피벗을 선택하기 위해 Median of Medians 알고리즘을 사용하면 최악의 경우에도 O(n)의 시간 복잡도를 보장할 수 있다.
  • 그러나 상수 계수가 커서 실제로는 무작위 피벗 선택이 더 효율적일 수 있다.

5. 결론

선형 시간 선택 알고리즘은 퀵 정렬의 분할 방식을 활용하여 정렬되지 않은 배열에서 원하는 순서의 요소를 효율적으로 찾을 수 있다. 평균적으로 O(n)의 시간 복잡도를 가지며, 추가적인 메모리 공간을 필요로 하지 않는다. 무작위 피벗 선택을 통해 최악의 경우를 피할 수 있으며, 큰 데이터 집합에서 효율적으로 동작한다. 그러나 최악의 경우 O(n^2)의 시간 복잡도를 가질 수 있으므로, 이러한 상황을 방지하기 위한 추가적인 전략이 필요할 수 있다.