Problem Set 6

1. Solve the exercise problem 14 of the chapter 7.

합병정렬 알고리즘은 분할정복(divide and conquer) 방식을 사용하여 리스트를 반으로 나눈 후, 각각을 재귀적으로 정렬하고 다시 합병(merge)하는 과정을 반복하여 정렬을 수행합니다.

합병하는 과정에서 레코드를 비교하고 저장하게 되는데, 두 개의 리스트를 비교하면서 작은 값을 새로운 리스트에 저장하는 것을 반복합니다. 이때 레코드의 저장 횟수는 입력 크기 n에 비례합니다.

따라서, 합병정렬 알고리즘의 시간 복잡도는 두 개의 리스트를 합병하는 과정에서 레코드를 저장하는 횟수인 2n에 로그를 씌운 nlgn이 됩니다.

따라서, T(n) = 2nlgn으로 나타낼 수 있습니다.

 

• 파이썬에서 구현된 합병정렬 알고리즘의 코드를 살펴보겠습니다.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

위 코드에서 merge_sort 함수는 리스트 arr을 입력으로 받아 합병정렬을 수행합니다.

먼저, 리스트의 길이가 1보다 큰 경우, 리스트를 반으로 나누고 각각의 리스트를 merge_sort 함수를 재귀적으로 호출합니다. 이 과정에서 입력 리스트가 점점 작은 크기로 나누어지고, 결국에는 길이가 1인 리스트들이 여러 개 생기게 됩니다.

이후, 두 개의 리스트를 합병하는 과정에서, 각 리스트의 첫번째 인덱스부터 비교하여 작은 값을 새로운 리스트에 저장하게 됩니다. 이때, 레코드의 저장 횟수는 새로운 리스트의 크기 n에 비례하게 됩니다.

따라서, 합병정렬 알고리즘의 시간 복잡도는 리스트를 반으로 나누는 과정에서는 비교만 하기 때문에 O(lgn)이 소요되며, 두 개의 리스트를 합병하는 과정에서는 레코드를 저장하는 횟수가 n번이 소요되기 때문에 O(n)이 소요됩니다. 그리고 이 과정이 n개의 요소를 가진 리스트에 대해 수행되기 때문에, 전체적인 시간 복잡도는 O(nlgn)이 됩니다.

즉, T(n) = 2nlgn이 됩니다.