Quick Select를 O(n)에 구현 가능한 Median of Medians 알고리즘

2jinishappy.tistory.com/124

Array의 k번째 작은 element 찾기 - QuickSelect 알고리즘

이전 포스팅에서 배열에서 k번째로 작은 element를 찾아내는 Quick Select 알고리즘을 알아봤다.

Quick Select를 진행하면서 선정한 pivot이 너무 작거나 크다면, partitioning이 제대로 이루어지지 않아 Worst-Case에 O(n²)이 소모됨을 확인했다

그렇기 때문에, Quick Select의 성능은 'good pivot을 얼마나 빨리 찾아내느냐'에 달려있다

이번에 다룰 Median of Medians 알고리즘은 good pivot을 worst-case O(n)에 찾아내는 알고리즘이다.

해당 알고리즘의 과정은 다음과 같다

출처: 위키피디아

0️⃣ Array의 size가 25 이하일 경우에는, Array를 sort하여 selection한다

1️⃣ Array의 Size가 25를 넘을 경우, Array를 size가 5인 n/5개의 subarray들로 분할한다.

2️⃣ 각 subarray들의 median을 찾은 후, 이를 M(medians) Array에 저장한다. (이 때, median을 찾기 위해 sort 알고리즘을 사용해도 무방)

3️⃣ M의 median을 quickselect using median of medians로 찾아내고(0번부터 재귀 호출) 이를 pivot으로 선정한다

4️⃣ pivot 선정 이후의 quickselect 알고리즘을 적용하여 k번째 작은 element를 반환한다

 

 

이 때, 0️⃣번과 2️⃣번의 input size는 상수(25, 5)이기 때문에 시간복잡도는 O(1) (이론상) 소모된다고 할 수 있다 ❗

C++로 구현한 코드는 아래와 같다

int medianOfFive(vector<int> arr) {
	sort(arr.begin(), arr.end());
	return arr[arr.size() / 2];
}
int momSelect(vector<int> arr, int k) {
	if (arr.size() <= 25) {	//배열의 크기가 25 이하일 경우에는 sort해서 반환
		sort(arr.begin(), arr.end());
		return arr[k - 1];
	}

	int m = (arr.size() + 4) / 5;
	vector<int> M;	//medians를 모아놓을 배열

	for (int i = 0; i < m; i++) {
		vector<int> sub;
		for (int j = 0; j < 5; j++)
			if ((5 * i + j) < arr.size())
				sub.push_back(arr[5 * i + j]);
		M.push_back(medianOfFive(sub));	//subarray의 median M배열에 추가
	}
	int mom = momSelect(M, m / 2);
	//mom을 quickSelect를 재귀 호출해서 찾아낸다

	int pivot = mom;	//uniformly randomize한 element를 pivot으로 설정
	vector<int> A1, A2;

	for (auto x : arr) {
		//pivot을 기준으로 element partitioning
		if (x < pivot)
			A1.push_back(x);
		else if (x > pivot)
			A2.push_back(x);
	}

	if (k <= A1.size())	//찾고자 하는 answer가 A1에 있을 경우 subproblem 호출
		return momSelect(A1, k);
	else if (k == A1.size() + 1)	//현재 problem의 answer가 pivot일 경우 반환
		return pivot;
	else 	// 찾고자 하는 answer가 A2에 있을 경우 subproblem 호출
		return momSelect(A2, k - (A1.size() + 1));

}

 

이제 Quickselect using median of medians의 Time Complexity를 분석해본다

quickselect의 성능은 good pivot의 선정에 따른다고 했는데, MoM은 얼마나 good한(❓) pivot일까 🤔

보통의 array 상태는 맨 첫 번째 표와 같지만, time complexity 분석을 위해 임의로 'array가 정렬되어 있다'고 가정한다. 표는 위에서 아래 방향의 오름차순으로 정렬되어 있고, 노란색 부분 또한 왼쪽에서 오른쪽으로 정렬되어 있다고 한다. 이 경우, 당연히 mom(median of medians)은 파란색 element가 된다.

그리고, array가 sort되어 있기 때문에 왼쪽 초록색 박스에 속한 element는 무조건 mom보다 작다. 마찬가지로, 오른쪽 초록색 박스에 속한 element 또한 mom보다 무조건 크다.

Array의 input size를 n이라고 했을 때, 초록색 박스의 size는 둘다 3n/10이다(3/5n * 1/2). 그리고, mom을 선택했을 경우 subproblem의 크기는 (원래 input size) - (A1, A2중 하나의 size)가 되기 때문에, 이 경우 subproblem의 크기는 최대 ( n - 3n/10 )이 되어 7n/10이 된다

따라서 T(n)을 size가 n인 array에서 quickselect with median of medians를 하는 데 걸리는 worst-case time이라 했을 때

T(n) = T(n/5) + T(7n/10) + O(n)

T(n/5) : Array M에서 subproblem(subarray의 medians들 중 median 찾기) 해결
T(7n/10) : pivot(mom) 선정 후 결정된 subproblem의 최대 크기
O(n) : n/5개의 배열 sort하는데 걸리는 시간( subarray n/5개 * O(1) <- 5개의 array sort 시간 )

∴ T(n) ≤ T(9n/10) + O(n)이고, master theorem에 의해 T(n) = O(n)이다.

이 된다.

이처럼, size n의 array중 k번째 작은 element를 찾는데 worst-case에도 O(n)의 시간밖에 걸리지 않는다 😱 라고 생각할 수 있지만, 실제 성능은 매우 느리다.

이유는 n/5개의 배열을 sort하고, input size가 25개 이하일 때 sort하는 과정을 상수 시간 처리했지만 이 상수 시간이 실험적으로는 매우매우 크기 때문이다 💯

하지만 이론적으로는 QuickSelect를 median of medians을 이용해서 pivot을 선정했을 때 worst-case O(n)에 구현 가능하기 때문에 굉장히 중요한 알고리즘이다(라고 들었다)

😉