[알고리즘] 병합정렬(MergeSort) 시간복잡도

[ 점화식으로 구하기 ]

 

T(N) = 데이터 N개일때  해당 알고리즘에서 걸리는 시간 이다.

 

여기서 N개 알고리즘은 1/2N 개를 다시 합친것으로 

위와 같은 수식으로 표현이 가능하다.

즉, 재귀적으로 표현할 수 있다.

 

이제 T(N/2^K)를 T(1)로 만들기 위해 N=2^K 라고 가정하면

K = log2n임을 얻을 수 있고

이를 대입하여 O(N*log2N) 임을 얻을 수 있다.

 

---

[ 노가다로 구하기 ]

 

참고로 난 점화식 세워서 하는걸 추천...

이 방법은 항상 골치 아파요...

 

빅오 = 최악의 상황 + 핵심적인 비교연산 코드 찾기

 

여기서 MergeSort 함수에서 분할(Divide) 을 담당하고

MergeTwoArea 함수에서 병합( Merge / Conquer )을 담당한다

 

하지만 MergeSort 함수는 신경쓸 필요가 없다!

시간복잡도 계산 시 고려사항이 아니다!

 

왜냐하면 MergeSort는 무지성으로 둘로 나눠 쪼개는 함수이기 때문에

우리가 찾는 핵심적인 비교연산 코드가 없기 때문이다!

 

따라서 시간복잡도는 MergeTwoArea 만 계산해주면 된다.

 

 

 

 

 

그럼 MergeTwoArea 함수를 보자.

 

void MergeTwoArea(int* arr, int left, int mid, int right) {
	int fIdx = left;
	int rIdx = mid+1;
	// startindex
	int sIdx = left;

	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));

	int i = 0;

	while (fIdx <= mid && rIdx <= right) {
		if (arr[fIdx] <= arr[rIdx]) {
			sortArr[sIdx++] = arr[fIdx++];
		}
		else {
			sortArr[sIdx++] = arr[rIdx++];
		}
	}

	if (fIdx > mid) {
		for (int k = rIdx; k <=right; k++) {
			sortArr[sIdx++] = arr[k];
		}
	}else{
		for (int k = fIdx; k <= mid; k++) {
			sortArr[sIdx++] = arr[k];
		}
	}
    
	for (int k = left; k <= right; k++) {
		arr[k] = sortArr[k];
	}
	free(sortArr);
}

 

이 함수에서 가장 핵심적인 비교연산 코드는 아래와 같다.

while (fIdx <= mid && rIdx <= right) { //code }

 

최악의 상황은 이 코드를 최대한 많이 도는 것이다.

 

그럼 이 같은 최악의 상황은 언제 벌어질까?

 

바로 fIdx와 rIdx 가 번갈아가며 한 번씩 증가(fIdx), 감소(rIdx) 하는 것이다.

 

그럼 다음과 같이 정렬 데이터가 n개일때는 n번은 비교연산이 최악의 경우라는 것을 알 수 있다.

 

굳이 저렇게 곡선 그려가며 안해도 된다.

다음과 같이 X표 치면서 그려나가면 더 쉽게 파악할 수 있다.

 

이렇게 하면 규칙이 보인다

 

묶는 개수만큼 비교연산 개수가 나오고 

거기다 묶음 수 까지 곱하면 모든 단계에서 나오는 비교연산 횟수는 

정렬해야하는 총 원소개수(n)과 같다는 것이다.

 

그럼 총 단계의 수는 log2n이니 최종 빅오는 n*log2n이 나온다!!

 

결과론적인 얘기로 접근해보면

 

n*log2n 에서 

 

n은 한 단계에서 걸리는 최악의 비교연산 횟수, 즉 변수라고 볼 수 있고

 

log2n은 단계수, 2묶음씩 병합할때 나오는 총 횟수이므로 상수라고 볼 수 있다!

 

따라서 변수*상수 이므로 우리가 공들여서 계산해야할 것은 

 

한 단계에서 나오는 비교연산 횟수라고 볼 수 있다!!

 

이렇게 생각하면 다른 정렬들도 이런 시각으로 접근해볼 수 있다.

 

이진트리, 이진구조로 된 알고리즘들은 

 

보통 log2n이 빅오에 포함되어 있는데 

 

그럼 log2n 외 변수는 한 단계에서 나오는 최악의 상황 횟수라고 볼 수 있다!

 

---

 

하지만 이렇게 노가다 하는 것보다 

그냥 T(N) 식 세워서 구하는게 훨씬 빠르고 편리하다.

 

이렇게 노가다 하는 건 진짜 감이 안올때만...