Chapter11 알고리즘 성능 분석

11.1.1 알고리즘 성능측정기준

1. 정확성 : 정확하게 동작하는가?
2. 작업량 : 얼마나 적은 연산을 수행하는가? (정렬 : 비교횟수, 탐색 : 거치는 노드개수)
3. 메모리 사용량 : 얼마나 적은 메모리를 사용하는가?
4. 단순성 : 얼마나 단순한가?
5. 최적성 : 더 이상 개선할 여지가 없을 만큼 최적화되어 있는가?

알고리즘 수행시간

1. 최악의 경우 O
2. 평균의 경우 Omega
3. 최선의 경우 Theta

재귀 알고리즘의 수행시간
팩토리얼을 재귀 방정식으로 나타내면
1 (n=0,n=1)
f(n)=f(n-1)*n (n>1)

int RecurrenceSum( int Data[], int SizeOfData) {
	if(SizeOfData==1)
		return Data[0];
	else
		return RecurrenceSum(&Data[1], SizeOfData-1)+Data[0]
}

&arr[4],1 = (arr[4])
&arr[3],2 = (&arr[4],1)+arr[3]
&arr[2],3 = (&arr[3],2)+arr[2]
&arr[1],4 = (&arr[2],3)+arr[1]
&arr[0],5 = (&arr[1],4)+arr[0] 입력데이터 n에 대한 알고리즘 수행시간을 T(n)이라고 하면, 데이터의 크기가 1보다 큰 경우 T(n)은 다음과 같이 정의할 수 있다.
T(n) = T(n-1) + c
(c는 재귀호출 비용 외에 알고리즘에서 요구하는 처리비용, 위 코드에서는 재귀호출 결과와 Data[0]을 더한 비용)

이 식을 펼쳐보면
T(n)= T(n-1)+c
= T(n-2)+c+c = T(n-2)+2c
= …=T(2)+(n-2)c
= T(1)+(n-1)c
<= c+(n-1)c=cn
따라서 T(n) <=cn
빅오표기법은 O(n)

즉,재귀알고리즘에서 알고리즘을 다 도는 데 걸리는 시간
T(n)=cn
O(n)
대충 알고리즘 도는 걸 다 더하면 된다는 거

11.3.2 퀵 정렬의 성능분석

성능 분석 대상은 비교 작업량

void QuickSort(int DataSet[], int Left, int Right){
	if (Left < Right) {
		int Index = Partition(DataSet, Left, Right);

		QuickSort(DataSet, Left, Index -1);
		QuickSort(DataSet, Index+1, Right);
	}
}

최선의 경우 완전이진트리
알고리즘 돌아가는 거 다 합하면
n
n/2+n/2 =n
n/4 *4 =n
…
각 레벨마다 n인데 깊이가 logn
따라서 T(n)=nlogn