언제나 휴일

6.1 병합 정렬 알고리즘 성능 분석병합 정렬 알고리즘 성능을 분석해 보아요. 병합 정렬은 배열의 원소가 1개일 때까지 분할하죠. 분할한 두 개의 배열을 하나로 합치기 위해서는 두 배열의 원소 개수만큼 비교해요. 원래 배열을 분할한 배열을 합치기 위해 비교는 n번 수행하겠죠. 결국 분할 횟수 * n 만큼 수행해요. 분할은 원속 개수를 n=>n/2=>n/4... 형태로 분할하므로 2의 h 승이 1이 될 때까지 분할하죠. 수행 속도는 h*n 이예요. 2의 h 승이 n이므로 h는 logn예요. 따라서 수행 속도는 O(nlogn)이라고 말할 수 있어요.

5.1 퀵 정렬 알고리즘 성능 분석 퀵 정렬 알고리즘 성능을 분석합시다. n 개의 원소인 배열을 정렬할 때 걸리는 수행 시간을 T(n)이라고 합시다. 퀵 정렬은 재귀적인 방법으로 해결하고 반 씩 나누어 재귀 호출이 이루어지는데 재귀 호출이 진행하기 전에 비교에 걸리는 시간을 S(n)이라고 합시다. 그리고 n 개인 원소를 재귀 호출 전에 비교하는 횟수는 n번이므로 S(n)=n입니다. T(n) = 2*T(n/2) + n = n^2T(n/n^2) + 2*n = ... = h*n 재귀는 원소 개수가 1보다 작으면 탈출하므로 n^h =1 일 때 더 이상 재귀 호출은 발생하지 않습니다. h = logn이므로 T(n) = nlogn 그런데 이처럼 퀵 정렬에서 재귀 호출 시에 절반으로 나누어지는 것은 피벗을 잘 선택하..