L07 - Selection

 

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한
 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다

 

 

 

Selection Problem

 

Problem Definition

 

(정렬되지 않은) 배열 arr에서 i 번째로 작은 값 찾기

Input : arr, i (0 <= i < n)
(여기서 i는 0부터 시작한다는 점을 염두하자)

Output : arr에서 i 번째로 작은 값

 

생각해볼 수 있는 Methods 로는

 

1. 최솟값 찾기를 반복

=> 최악의 경우 시간 복잡도 Θ(i×n) = Θ(n^2)

(최악의 경우 i가 n-1 이므로)

2. 정렬 후 i 번째 값 찾기

 

=> 정렬하는데 필요한 시간 Θ(n logn) 

 

Heapsort 사용시 Θ(n + i logn)

(build-heap을 하고 뽑는데 logn 걸리는게 i 번 반복되므로)

 

그렇다면 Lower bound 는?

 

배열의 모든 값을 최소 한 번은 살펴봐야 하므로 Ω(n)로 볼 수 있음

 

=> i 번째로 작은 값을 Θ(n)에 찾을 수 있을까를 생각해봐야함!

 

Linear Time Algorithm in Expectation

 

Quickselect

 

Quicksort의 Partition 함수는 pivot을 제자리에 놓음!

 

(이 때 Partition 함수는 배열 arr의 요소의 개수 n만큼 돌면서 비교를 하므로 Θ(n)로 볼 수 있음)

 

Quicksort의 Partition 함수

 

 

 

 

키포인트는 pivot의 위치 i가 의미하는게 곧 i 번째로 작은 값이라는 것임!

 

이를 토대로 case를 나눠보면

 

Case 1 : i가 Pivot의 위치와 동일하다면 pivot을 그대로 return

 

Case 2 : (i < Pivot의 위치) 라면 pivot의 왼쪽에서 재귀 반복

 

Case 3 : (i > Pivot의 위치) 라면 pivot의 오른쪽에서 재귀 반복

 

 

Quickselect 흐름

 

 

처음에 오른쪽 맨 끝에 있는 10을 pivot으로 위치를 찾고 

 

10의 위치가 i = 7 이므로 i = 3 번째로 작은 값을 찾으려면 왼쪽에서 재귀적으로 실행

(Case 2)

 

그 다음 pivot인 3의 위치를 찾고

 

3의 위치가 i = 2 이므로 i = 3 번째로 작은 값을 찾으려면 오른쪽에서 재귀적으로 실행 

(Case 3)

 

그 다음 pivot인 9의 위치를 찾고

 

9의 위치가 i = 6 이므로 i = 3 번째로 작은 값을 찾으려면 왼쪽에서 재귀적으로 실행

(Case 2)

 

그 다음 pivot인 6의 위치를 찾고

 

6의 위치가 i = 3 이므로 i = 3 번째로 작은 값이 6인걸 알게됬고 이를 return

(Case 1)

 

 

Complexity Analysis of Quickselect

 

최선의 경우 Θ(n) 

 

=> pivot이 딱 i 번째로 작은 값인 경우

(partition 함수가 Θ(n) 이므로 한 번만에 성공)

 

최악의 경우 Θ(n^2)

 

=> pivot이 i와 정 반대에 있는 경우

 

i = 0 인데 pivot이 항상 가장 큰 값인 경우에는 n + (n - 1) + (n - 2) + ... = Θ(n^2)

 

 

평균 시간 복잡도 Θ(n)

 

pivot이 k번째로 작은 값이라면

 

 

T(n) <= max(T(k), T(n - k - 1)) + c0n

 

=> 최악의 경우를 평가하기 위해 max를 이용해 두 가지 부분 중 더 큰 복잡도를 사용
(그래서 T(n)이 최악의 경우보다는 작거나 같다고 봄)

 

이 때 c0n 은 partition 하는 과정의 오버헤드로 보면 됨

(단순히 배열을 순회하는 시간 외에, 피벗을 선택하고, 요소를 비교하고, 적절한 위치로 이동시키는 데 드는 시간까지 포함)

 

pivot의 위치 k가 0 ~ n-1 사이에 고르게 분포한다 가정

 

 

 

 

평균을 구하기 위해 k = 0 부터 n - 1까지 (배열의 인덱스 범위)를 n으로 나눴음

 

T(k)와 T(n-k-1) 을 k = 0 ~ (n - 1) 까지의 경우로 생각해보면

대칭성을 가지고 있다는걸 알 수 있음

 

T(0) 과 T(n - 1) , T(1) 과 T(n - 2) , T(2) 과 T(n - 3) , ... , T(n - 3) 과 T(2) , T(n - 2) 과 T(1) , T(n - 1) 과 T(0)

 

이를 절반으로 나누면 k = 0 ~ (n / 2) - 1 과 k = n / 2 ~ n - 1

 

이 의미는 k = 0 ~ (n - 1) 까지의 합은 k = n / 2 ~ n - 1 까지의 합에 2를 곱하면 됨 (대칭성)

하지만 n / 2는 n이 짝수일 경우는 정확히 절반이지만 홀수인 경우는 k = n/2 ~ n - 1 쪽이 앞쪽에 비해 더 큰 것을 볼 수 있음

즉, k = ⌊n / 2⌋ ~ n - 1 까지의 합에 2를 곱한건 k = 0 ~ n - 1 까지의 합보다 크거나 같음

 

그래서 결국 

 

 

이런 식이 나오게 되는 거임

 

최선의 경우에서 Ω(n) 임을 알았기 때문에, 평균적인 경우에 대해서도 시간 복잡도가 O(n) 임을 보이면 Θ(n)를 만족하게 됨

=> ⌊n/2⌋ ≤ k < n 인 k에 대해 T(k) ≤ c2k를 만족한다 가정하고 귀납 증명을 하면 됨!

 

 

 

Linear Time Algorithm in the Worst Case

 

Observation on Partitioning

 

Partition 함수가 입력을 항상 1 : 9의 비율로 나누며, i가 항상 9 부분에 속한다면 복잡도는?

 

 

T(n) = T ( 9/10 n ) + c0n

 

으로 볼 수 있음

 

이는 Master Theorem의 case 3에 의해 Θ(n)

(1 : 99의 비율로 나누는 경우도 동일)

 

 

https://hanjungyo.tistory.com/80#Master%20Method%20(Master%20theorem%20%EC%9D%B4%EC%9A%A9)-1

L02 - Recurrences

 

=> Master Theorem 관련 내용

 

 

여기서 알 수 있는 점은

비율이 좀 기울어져 있어도 입력을 특정 비율로 나누면 Θ(n) 을 유지한다

(단, 나누는 overhead가 O(n)이여야 함!)

 

 

Median of Medians

 

Partition할 때 입력을 작은 (5개씩) 그룹으로 나누어 각 그룹마다 중앙값을 구하고, 모든 중앙값들의 중앙값을 Pivot으로 사용!

 

 

 

 

Partition할 때 5개씩 묶어서 그룹으로 나누었고 (개수가 부족한 부분은 2개만)

 

그 (해당 그룹에 속한 5개의 수) 중에서 중앙값들을 찾음

 

그 후 또, 그 (각 그룹들의 중앙값) 중앙값을 Pivot으로 사용함

(중앙값들의 중앙값)

 

이렇게 하면 Pivot이 반드시 30% ~ 70% 위치에 있음을 보장

 

1. Pivot을 찾는데 Θ(n) 만큼 시간이 걸림

2. 특정 비율로 나눠짐 (아무리 큰 부분이더라도 결국 70% 30%로 쪼개짐)

 

=>  Worst Case에서도 특정 비율로 나눠지므로 Θ(n) 임

 

Median of Medians pseudocode

 

 

처음 부분에서는 5로 나누어 떨어지지 않으면 큰 값들은 뒤로 보내서 Median of Medians 를 찾을 때 제외시킴

 

(배열의 MOM 적용 범위를 5의 배수로 만들어줌)

 

=> 이 때 그냥 제외시키는게 아니라 찾으려는 i번째 값이 일치하면 해당 값을 바로 return

 

그 후 남아있는 데이터들은 5개씩 묶어 n/5 개의 그룹으로 나누고

 

각 그룹마다 중앙값을 구한 후 그것들의 중앙값을 재귀적으로 구함

 

이 때 구한 중앙값의 중앙값을 pivot으로 선정 (배열의 가장 뒤에 놓고 quickselect 실행)

 

Worst Case Secnario

 

왜 이 방식은 30% ~ 70% 위치에 Pivot이 있음을 보장할까?

 

 

MoM을 찾으면 주황색 박스가 있는 줄 (각 그룹들의 중앙값) 에서 15보다 왼쪽에 있는 3개의 값 (중앙값들) 은 15보다 작을것이고 오른쪽에 있는 3개의 값 (중앙값들) 은 15보다 클 것임

=> 이는 M이 중앙값들 중에서 중앙값이기 때문에 당연함

 

 그리고 파란색 점선으로 표시된 부분은 15보다 크고 빨간색 점선으로 표시된 부분은 15보다 작을 수 밖에 없음

 

=> 각 그룹의 중앙값보다 크거나 작은 값들일테니까

 

왼쪽의 회색 점선 부분은 각 그룹에서 중앙값보다 클테지만 그 중앙값이 15보다는 작은 중앙값일테니 크다 작다를 판별할 수 없음

오른쪽의 회색 점선 부분은 각 그룹에서 중앙값보다 작을테지만 그 중앙값이 15보다는 큰 중앙값일테니 크다 작다를 판별할 수 없음

 

 

Worst Case

 

그렇다면 최악의 경우를 살펴보면

 

Median(위 그림에서는 M) 보다 큰지 작은지 몰랐던 회색 점선 부분이 전부 M보다 큰 경우를 생각해볼 수 있음

 

전체 데이터 수를 n이라고 하고 그룹의 수 n / 5 는 g라고 하면

 

빨간색 점선 부분과 파란색 점선 부분의 크기를 정의해볼 수 있는데

 

빨간색 부분은 (3/2) * g 보다 크거나 같으므로

 

파란색 부분은 전체 5 * g 에서 (3/2) * g 를 뺀 (7/2) * g 보다는 작거나 같음

 

g를 n으로 바꾸면 파란색 부분 (Worst case에서 M보다 큰 부분) 은 (7 / 10) * n 보다 작거나 같음

 

=> 70% : 30% 가 보장됨

 

Complexity Analysis

 

Median of Medians pseudocode

 

 

위 코드에서 살펴보면 momselect를 재귀적으로 호출하는 부분이 2군데 있는데

 

초록색 글씨의 3번에서 momselect를 호출하는건 

 

전체 데이터 n중에서 5로 나눈 애들 만큼만 찾고 있으므로 T(n/5) 이 되고

(중앙값의 중앙값을 찾는거니까)

 

밑의 quickselect 하는 부분에서 momselect를 재귀적으로 호출하는건

 

최악의 경우에도 pivot이 항상 (7 / 10) * n 보다는 작거나 같은 위치에 있는 것을 알고 있으므로 T((7 / 10) * n) 보다 작거나 같음

 

partition과 MoM 과정에서의 오버헤드 = c0n

 

 

 

즉, 최악의 경우에 시간 복잡도는 O(n)임