[알고리즘] Divide and Conquer - Binary Search | Merge Sort

학교에서 들은 알고리즘 분석 강의 내용을 복습하면서 작성한 글입니다.
March 14, 2024 5:54 PM

Divide-and-Conquer

Binary Search

• 중간 값 기준으로 반쪽 날림 → shrink
• f(n)=f(n/2)+1
• →log n번만 비교해도 ok : sequential search보다 훨씬 효율적

• 이진 탐색의 각 탐색 단계마다 탐색 범위가 절반으로 줄어들기 때문에, 로그함수적으로 줄어들다가 K번 째 단계에서 배열의 크기가 n/(2^k) = 1 이 됨 (이유: 탐색이 완료되기 위해서는 탐색범위가 1이어야 하기 때문) → n = 2^k 양변에 로그 취하면,
• k=logn -> 시간복잡도: logn

index location(index low, index high)
{
	index mid;
	if (low > high)
		return 0;
	else{
		mid = (low+high)/2 ;
		if (x == S[mid])
			return mid;
		else if(x<S[mid])
			return location(low, mid-1); //왼쪽부분으로 다시 recursion
		else
			return location(mid+1, high);
		}
	}

---

MergeSort

• array를 2개의 subarray로 divide
• 각각의 subarray 를 sorting → 1개짜리 리스트가 되면 이미 sort되었다는 것!n
• 2개의 sort된 subarray를 merge

→ lower bound 아님. sorting의 lower bound는 1~n-1까지 비교하는 것

void mergesort(index low, index high)
{
	index mid;
	if(low<high){
		mid = (low+high)/2;
		mergesort(low, mid);
		mergesort(mid+1, high);
		merge(low, mid, high);
	}
}

void merge(index low, index mid, index high)
{
	index i,j,k;
	keytype U[low...high];
	i=low; j=mid+1; k=low;
	while (i <= mid && j <= high){
		if(S[i]<S[j]){
			U[k] = S[i];
			i++;
		}
		else{
			U[k] = S[j];
			j++;
		}
		k++;
	}
	if (i>mid)
		move S[j] through S[high] to U[k] through U[high];
	else
		move S[i] through S[mid] to U[k] through U[high];
	move U[low] through U[high] to S[low] through S[high];
}

•  정렬 알고리즘 별 시간복잡도