머지 소트의 시간복잡도
머지소트는 분할 정복 카테고리에 속합니다.
숫자로 이루어진 수열이 반씩 나눠지며 하나만 남게 되는 과정이 분할이고,
각 파티션끼리 합쳐지는 과정이 정복입니다.
머지 소트의 시간복잡도는 O(NlogN)이라고 잘 알려져 있습니다.
왜 O(NlogN)일까요?
우선, 분할과정을 살펴봅시다.
단순히 생각해서 7개의 숫자로 이루어진 수열에서 숫자를 하나씩 떼어내려면 총 6번을 하나씩 떼어내야 합니다.
7보다 1만큼 작은 이유는 마지막에 숫자 두개만 남았을 때 한번만 떼어내면 되기 때문입니다.
숫자가 N개 있으면 N-1번 떼어내야 합니다.
따라서 N에 대해 선형적이므로 분할 과정은 O(N)입니다.
이제 정복 과정을 살펴봅시다.
정복은 같은 레벨의 파티션들을 쌍을 이룬 후, 정렬하며 하나의 파티션으로 병합하는 과정입니다.
시간복잡도를 구하기 위해 일단 정복 과정의 높이를 구해야 합니다.
예를 들어, 숫자가 8개 였다면, 1 -> 2 -> 4 -> 8 이렇게 2를 3번 제곱하면 숫자가 8이 됩니다.
이를 수식으로 나타내면 1 * (2)^3 = 8 이 됩니다.
여기서 8 = N으로 바꾸고 3 = H로 바꾸면 N = 2^H 에서 H = logN 임을 알 수 있습니다.
여기서 H는 정복 과정의 높이, 즉 병합이 몇 층으로 이루어져 있는지를 나타냅니다.
이제 구해야 할 것은 각 층에서 몇 번의 숫자 비교를 거치는지 입니다.
분할된 각 층에서 짝 파티션끼리 숫자 비교를 하는데
한쪽 파티션 숫자들이 모두 다른쪽 파티션 숫자보다 작아서 최소 비교횟수로 한다고 치면 N/2회고,
지그재그로 숫자가 선택된다면 N입니다.
최대라고 쳐도 N이므로 각 층별 정렬 과정은 O(N)입니다.
그런데 층의 개수는 이전에 계산했던 logN개이고, 각 층마다 O(N)의 정렬이 이루어지므로 둘을 곱해주면 O(NlogN)이 정복의 시간복잡도입니다.
그래서 머지 소트의 시간복잡도는 분할과 정복을 합쳐 O(NlogN + N)인데 최고차항만 살리면 O(NlogN)이 됩니다.
예시
정렬할 원소의 개수 n이 64개라고 하자.
1. 분할 단계
- 먼저 64개의 원소를 각각 1개의 원소를 가진 64개의 부분 리스트로 나눕니다. 이를 위해서는 log64 = 6번의 분할이 필요합니다.
2. 정복 단계
- 분할된 64개의 부분 리스트를 다시 정렬된 하나의 리스트로 합치는 과정입니다.
- 가장 아래 단계에서는 64개의 부분 리스트를 32개의 정렬된 부분 리스트로 만들기 위해 최대 32번의 비교가 필요합니다.
- 그 다음 단계에서 32개의 정렬된 부분 리스트를 16개의 정렬된 부분 리스트로 만들기 위해 최대 64번의 비교가 필요합니다.
- 이런식으로 계속해서 위로 올라가며 비교를 하게 되는데, 최종적으로 2개의 정렬된 부분 리스트(각각 32개의 원소)를 하나의 정렬된 리스트로 만들기 위해 최대 64번의 비교가 필요합니다.
따라서 정복 단계에서 최대 64번의 비교를 6번(log64) 해야 합니다.
결론적으로 시간 복잡도는 최대 64log64가 됩니다. 이를 일반화하면 NlogN이 되어 머지 소트의 시간 복잡도는 O(NlogN)이 됩니다.
정리하면, 머지 소트는 분할 단계에서 logN번의 분할이 필요하고, 정복 단계에서 각 단계마다 최대 N번의 비교가 필요합니다. 따라서 전체 시간 복잡도는 O(NlogN)이 되는 것입니다.
예상 의문점
왜 정복할 때 정렬이 최소 N/2이고 최대 N인가요?
- N = 64인 위의 예시에서, 크기가 2인 파티션으로 나뉘어진 상태일 때, 총 32개의 파티션이 있습니다. 크기가 2인 각 파티션끼리 비교하는 경우, 최소 비교 횟수는 한쪽 파티션이 다른쪽 파티션의 가장 작은 숫자보다 다 작은 경우이고, 이때는 2번 비교해서 한쪽 파티션이 이미 다 소모되었으면 나머지 파티션을 그냥 붙이면 되므로 비교가 2회에서 끝납니다. 그런데 이러한 파티션 쌍이 16개 있으므로 2*16 = 32번의 비교를 수행하면 됩니다. 32는 64의 절반이므로 일반화하면 N/2입니다.
- 반대로 최대 비교 횟수인 경우는 3번 비교를 하게되고, 3*16 = 48번의 비교를 하게 됩니다.
- N이 커질수록 3에 해당하는 숫자와 두 파티션 크기 합과의 차이 비율은 줄어들게 되고, 따라서 N번의 비교를 하게 됩니다.
- 더 간단히 생각하면, 한쪽이 다 작으면 파티션 1개 크기만큼만 비교하면 되므로 N/2이고, 지그재그로 크기가 섞여있으면 두 파티션을 모두 살펴야 하므로 N이 됩니다.