6.1 병합 정렬 알고리즘 성능 분석

6.1 병합 정렬 알고리즘 성능 분석

---

병합 정렬 알고리즘 성능을 분석해 보아요.

 

병합 정렬은 배열의 원소가 1개일 때까지 분할하죠.

분할한 두 개의 배열을 하나로 합치기 위해서는 두 배열의 원소 개수만큼 비교해요.

원래 배열을 분할한 배열을 합치기 위해 비교는 n번 수행하겠죠.

결국 분할 횟수 * n 만큼 수행해요.

분할은 원속 개수를 n=>n/2=>n/4... 형태로 분할하므로 2의 h 승이 1이 될 때까지 분할하죠.

수행 속도는 h*n 이예요.

2의 h 승이 n이므로 h는 logn예요.

따라서 수행 속도는 O(nlogn)이라고 말할 수 있어요.