교수님이해안돼요

머지소트의 시간복잡도는 왜 O(nlogn)인가?

치즈03 2025. 3. 9. 23:23

머지소트는 분할정복알고리즘(Divide and Conquer)의 대표적인 예시로, 시간복잡도가 O(nlogn)인 매우 효율적인 정렬 알고리즘이다. 왜 머지일까? 일단 주어진 배열을 원소가 1인 부분배열들로 나뉠때까지 계속 분할하다가, 그 부분배열들을 다시 합치며(merge) 정렬하는 방식이기 때문이다. 이 과정에서 자기 자신을 호출하는 재귀적 방식으로 분할과 합치기(merge)를 진행한다는게 특징적인데, 한마디로 머리 꽤나 깨지는 알고리즘이라는 의미다.(^____^)

컴퓨터 알고리즘 두번째 시간에는, 시간복잡도와 Big-O 표기법을 배웠고 정렬 알고리즘 중

머지소트(merge sort)에 대해 배웠다. 분명 구현하는 코드는 짧고 간단했지만 왜 이 머지소트의 시간복잡도가 O(nlogn)이 되는지 너무 빨리 넘어가버려서 이 부분에 대해 조금 고민해보는 시간을 가져보려한다.

일단 구현을 해보겠다. 다음은 내가 짠 코드다.

def merge_sort(arr):
    #base code
    if len(arr) == 1:
        return arr
    #divide with recursive
    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left,right)

def merge(left,right):
    sorted = []
    i=j=0
    while i<len(left) or j<len(right):
        if left[i] < right[j]:
            sorted.append(left[i])
            i+=1
        else:
            sorted.append(right[j])
            j+=1
    sorted에 남은 원소를 이어붙인다.
    return sorted

이제 이걸 교수님의 코드로 고치면,,

def merge_sort(arr):
    #base code
    if len(arr) <= 1: #>>>>>>>>>>>>>>>>>>>>>왜 ==가 아닌 <=로 할까?
        return arr
    #divide with recursive
    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left,right)

def merge(left,right):
    sorted = []
    i=j=0
    while i<len(left) and j<len(right): #>>>>>>>왜 or가 아니라 and지?
        if left[i] < right[j]:
            sorted.append(left[i])
            i+=1
        else:
            sorted.append(right[j])
            j+=1
    sorted.extend(left[i:]) #>>>>>>>extend 메소드는 처음 보네
    sorted.extend(right[j:])
    return sorted

크게 3개의 부분이 차이가 났다.

  • <=를 쓰는 이유: 배열이 빈 경우([])도 처리하기 위해서.(종료조건은 명확한게 좋지)
  • and를 쓰는 이유: 두 배열 중 하나라도 끝나면 반복을 멈추기 위해서.(아 이건 내가 코드를 잘 못 짰네)
  • extend()의 역할: 남은 원소들을 한 번에 리스트에 추가하기 위해서.
extend() 메소드는 뭘까?

extend()는 리스트를 확장하는 메소드로, 기존 리스트에 다른 리스트의 요소들을 개별 원소로 추가한다.

a = [1, 2, 3]
b = [4, 5]
a.extend(b)
print(a)  # [1, 2, 3, 4, 5]

 

코드에서 sorted.extend(left[i:])와 sorted.extend(right[j:])는 아직 정렬되지 않은 남은 원소들을 한 번에 추가하는 역할을 한다. 예를 들어, left = [1, 3, 5], right = [2, 4]이면 while문이 끝난 후 left의 5가 남을 수 있는데, 이걸 한 번에 extend()로 추가하는 거다. 이렇게 하면 append()를 반복적으로 쓰는 것보다 더 효율적이고 깔끔한 코드가 된다.

 

이제 본론으로 들어가서, 왜 이 merge sort가 O(nlogn)인지 알기 위해 원소가 8개인 배열을 예제로 어떻게 알고리즘이 동작하는지 살펴보겠다.

 

머지소트했을때 호출되는 함수를 트리구조로 표현했을 때 총 깊이는 2log2_n (분할 log2_n, 정복 log2_n)이다.

그럼 머지소트함수의 시간복잡도는 O(logn)인걸까? 정답은 `아니오`다.

시간복잡도는 일반적으로 최악의 경우(upper bound)의 총 반복횟수를 의미한다.

즉, 머지소트 알고리즘의 시간복잡도는 (재귀호출 횟수) + (while문 반복횟수)가 추가적으로 고려되어야한다.

실제로 n=8일때 위 그림처럼 시뮬레이션 한 결과,

 재귀호출횟수 :

  • (분할) 1 + 2 + 4 + 8 => 2n -1 => 15
  • (재귀)       4 + 2 + 1 => n - 1 => 7
  • 총 3n-1 = 22번

while 반복횟수(1번만 돈 것도 포함):

  • 4*1 (정복1단계) + 2*3(정복2단계) + 1*7(정복3단계)
  • 단계별 반복횟수가 n=8을 넘지 않고 비슷하니 8 + 8 + 8 => nlog2_n 으로 볼 수 있다.

정리하면 재귀호출횟수는 대략 3n-2, while문 반복횟수는 nlog2n이다.

즉, 핵심은 while문 반복횟수로, 전체 시간복잡도는 O(nlogn)으로 표기 가능하다.