알고리즘 강의에서 merge sort 병합 정렬을 배웠습니다.


MergeSort(A,p,r)

if p

then q <- [(p+r)/2]

MergeSort(A,p,q)

MergeSort(A,q+1,r)

Merge(A,p,q,r)


이 수도 코드에서 시간복잡도를 구하는데 

총 소요 시간이 cn+cnlogN이라고 합니다.


교수님 말씀으로는 배열 수가 n일 때

MergeSort가 재귀함수라 자기 자신의 함수를 호출하여

첫째 줄의 정렬 횟수가 cn이면

둘째 줄의 정렬 횟수는 c(n/2)의 2배인 cn이 되고

셋째 줄의 정렬 횟수는 c(n/4)의 4배인 cn이 되어서

간선횟수의 logN+1에 정렬 횟수를 곱하여 cn+cnlogN이 된 것이라고 하셨습니다.

자기 자신의 함수 호출하기 때문에 COST가 모두 c로 같다고 하셨습니다.


버블 정렬에서 정렬 횟수를 구할 때에는

첫째 줄 for i=0 to N 의 COST는 c1이라 탐색 횟수는 c1*(N+1)이고

둘째 줄에서 윗 줄 반복문에 삽입된 for j=0 to N 의 COST는 c2라 탐색 횟수는 c2(N+1)이었습니다.

각 줄마다 COST를 다르게 설정했었는데


MergeSort 함수도 각 줄마다 COST를 다르게 설정하지 않는 이유는 무엇인가요?

함수 내에서 함수를 호출하기 때문인가요?

재귀함수로 구성되어 있다고 해도 함수의 위치를 따지면 COST도 c1, c2, c3로 다르게 설정해야 되는 것 아닌가요?


교재 및 구글에서 영어로 자료도 찾아봤었는데 그냥 이렇게 된다 뿐이지

왜 저렇게 COST를 같이 설정해야 하는 이유는 알려져 있지 않았습니다.

참고할 만한 자료를 알려주시면 감사드리겠습니다.


위의 Pseudo Code는 Introduction to Algorithm에 있습니다.