Lecture 3: Sorting 정렬

검정색 볼드체: MIT에서 제공하는 자료에 나오는 내용 그대로 적음 

검은색 글자: 자료 내용 해석

파란색 글자: 자료에는 없지만 추가 설명을 적어 놓은 것 

Lecture 3: Sorting 

1. Set Interface 

이 전 강의에서 아이템 순서가 있는 인터페이스는 Sequence Interface이고, 

아이템 순서가 없지만 아이템 중복도 없는 인터페이스를 Set Interface라고 하였다. 

 

Container	build(X)	given an iterable X, build set from items in X
	len()	return the number of stored items
Static	find(k)	return the stored item with key k
Dynamic	insert(x)	add x to set (replace item with key x.key if one already exists)
	delete(k)	remove and return the stored item with key k
Order	iter_ord()	return the stored items one-by-one in key order
	find min()	return the stored item with smallest key
	find max()	return the stored item with largest key
	find next(k)	return the stored item with smallest key larger than k
	find prev(k)	return the stored item with largest key smaller than k

 

 

Storing items in an array in arbitrary order can implement a (not so efficient) set

배열에 아이템들을 임의의 순서(arbitrary order)로 넣으면, 그걸로 일종의 Set(중복 없는 집합)처럼 사용할 수 있다.

배열은 sequence interface로 아이템 순서가 있지만 아이템 중복도 가능하다. 

하지만 예를들어 [5, 2, 9, 1] 같은 배열에 중복 없는 값만 넣으면 set 역할도 가능하다.

하지만 효율적이지 않다. 왜냐하면 

• 중복 검사할 때 매번 배열을 순회해야 함 → O(n)
• 값 찾을 때도 선형 탐색 → O(n)

그래서 배열로 set 구현은 가능은 하지만 비효율적인 방법이다.

 

* arbitrary: 임의의 

 

Stored items sorted increasing by key allows:

만약 배열에 들어간 아이템들을 key 순으로 오름차순 정렬해두면, 몇 가지 성능 이점이 생긴다

 

– faster find min/max (at first and last index of array)

정렬된 배열에서는 빨리 최소값, 최대값을 찾을 수 있다

• 최소값(min) → 배열 첫 번째 인덱스 (array[0])
• 최대값(max) → 배열 마지막 인덱스 (array[n-1])

이걸 단순히 꺼내면 되니까 O(1) 시간에 최소값/최대값을 구할 수 있다

 

– faster finds via binary search: O(log n)

배열이 정렬되어 있으면, 특정 값 찾을 때 이진 탐색(binary search)을 사용할 수 있다

• 이진 탐색: 배열의 중간부터 검사하면서 절반씩 줄여나가기 때문에 → O(log n)
• 정렬되지 않은 배열에서의 선형 탐색 O(n)보다 훨씬 빠름

배열 상태 특징

정렬 안 됨 (arbitrary order)	set처럼 쓰려면 느리고 비효율적
정렬됨 (increasing by key)	min/max 빠르게 찾음, 이진 탐색 가능

 

• Container → 자료구조 생성/build
• Static → 검색
• Dynamic → 삽입/삭제
• Order → min, max, 이전, 다음 찾기

Sorted Array에서 build(x)가 n log n 인 이유? 

주어진 데이터 n개를 자료구조에 담을 때 

일단 배열에 데이터 집어넣기 O(n) (단순 복사) 한 후 정렬을 한다. 

일반적으로 O(n log n)

 

Merge Sort, Heap Sort 같은 효율적인 정렬 알고리즘들은 최선·평균·최악 시간 복잡도가 O(n log n).

단, 특수한 경우(예: 값 범위 제한된 counting sort, radix sort)에서 O(n)까지 나올 수는 있음.

 

But how to construct a sorted array efficiently?

 

2. Sorting

2-1 Sorting 이란?

Sorting(정렬)이란 데이터를 일정한 순서(오름차순, 내림차순 등)로 재배열하는 것을 말한다
예) 숫자: 5, 2, 9 → 2, 5, 9 (오름차순)

예) 문자: banana, apple, cherry → apple, banana, cherry (알파벳순)

2-2 Sorting 사용 하는 이유

우리가 정렬을 사용하는 이유는:

• 검색 속도를 높이기 위해 → 정렬된 데이터는 이진 탐색(binary search) 등 빠른 검색이 가능함
• 데이터를 보기 쉽게 만들기 위해 → 사용자에게 깔끔하게 보여줌
• 중복이나 패턴을 쉽게 찾기 위해 → 정렬하면 같은 값이 옆에 모이므로 비교·분석이 쉬워짐
• 알고리즘이나 다른 작업의 전처리로 사용하기 위해 → 예: 정렬 후 중복 제거, 병합 등

2-3 Set에서 Sorting 하는 이유

sequence는 순서 보존이 중요한 자료구조라서,

삽입한 순서랑 정렬된 순서를 섞어 관리하면 오히려 혼란스럽고 성능도 안 좋다. 

반면 Set은 어차피 순서가 없으니까

정렬된 버전(Set+정렬)으로 쓰면 중복도 없고, 정렬된 데이터로 효율적 관리 가능

특히 검색, 탐색에서 유리 (예: TreeSet은 log(n) 탐색, 삽입 가능)

 

Given a sorted array, we can leverage binary search to make an efficient set data structure.

정렬된 배열을 주어졌다면, 이진 탐색을 이용해 효율적인 집합 자료구조를 만들 수 있다.

 

2-3 Sorting 후 정렬된 아이템을 새 배열에 담는 경우 

Input: (static) array A of n numbers

입력: n개의 숫자를 담은 Static Array A가 주어진다. 

* Static Array는 Lecture 2에서 복습할 수 있습니다

 

Output: (static) array B which is a sorted permutation of A

아웃풋: A의 원소들을 정렬한 새로운 고정된 배열 B를 만든다.

 

– Permutation: array with same elements in a different order

순열이란 같은 원소를 가지고 있으나, 원소들의 순서가 다른 배열을 의미한다.

배열의 원소들은 같지만 순서만 바뀐 상태. 아래에서 좀 더 자세히 설명 

 

– Sorted: B[i − 1] ≤ B[i] for all i ∈ {1, . . . , n} (오름차순 정렬)

정렬된 배열이란, 모든 인덱스 i에 대해 앞의 원소가 뒤의 원소보다 작거나 같도록 배열된 상태를 뜻한다.

배열 원소들이 오름차순 혹은 내림차순으로 정렬되어 있음

모든 i에 대해 B[i-1] ≤ B[i] (오름차순일 때)

 

Example: [8, 2, 4, 9, 3] → [2, 3, 4, 8, 9]

예를 들어, 배열 [8, 2, 4, 9, 3]를 정렬하면 [2, 3, 4, 8, 9]가 된다.

[2, 3, 4, 8, 9] (오름차순 정렬일 때)

[9, 8, 4, 3, 2] (내림차순 정렬일 때)

 

2-4 Sorting 후 정렬된 아이템을 새 배열에 담지 않고 있는 배열 그대로 쓰는 경우 

A sort is destructive if it overwrites A (instead of making a new array B that is a sorted version of A)

정렬이 파괴적(destructive)이라 함은, 새로운 배열 B를 만들지 않고, 원래 배열 A 자체를 덮어써서 변경하는 것을 의미한다.

Destructive 정렬은 원래 배열 A를 직접 변경해서 정렬하는 모든 방법

 

A sort is in place if it uses O(1) extra space (implies destructive: in place ⊆ destructive)

정렬이 제자리(in-place)라 함은, 추가 메모리 사용이 상수(O(1)) 수준으로 매우 적은 경우를 말한다.

in-place 정렬은 destructive 정렬의 부분집합이다

In-place 정렬은 추가 공간 사용이 거의 없이 원래 배열을 직접 변경하는 정렬 방법

원본 배열을 덮어쓰기 때문에 in-place 정렬은 destructive 정렬중 하나이다

 

2-3-1 Permutation Sort

There are n! permutations of A, at least one of which is sorted

배열 A의 순열은 총 n!개가 존재하며, 그중 적어도 한 개는 정렬된 상태이다.

 

For each permutation, check whether sorted in Θ(n)

각 순열마다 정렬되어 있는지 여부를 Θ(n) 시간에 검사한다.

 

Example: [2, 3, 1] → {[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}

예를 들어, 배열 [2, 3, 1]의 모든 순열은 {[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}로 구성된다.

3! = 3 * 2 * 1 = 총 6개의 경우의 수 있음

1 def permutation_sort(A):
2     '''Sort A'''
3     for B in permutations(A):  # O(n!)- A의 모든 순열 B를 하나씩 생성
4         if is_sorted(B):       # O(n) - 현재 순열 B가 정렬되어 있는지 검사
5             return B           # O(1) - 정렬된 순열을 찾으면 즉시 반환

 

permutation sort analysis:

순열 정렬 알고리즘을 분석해 보면 

 

– Correct by case analysis: try all possibilities (Brute Force)

모든 경우의 수를 시도하여 올바른 결과를 보장한다. (완전 탐색 방식)

 

– Running time: Ω(n! · n) which is exponential :(

실행 시간은 최악의 경우 n!로, 지수 시간 복잡도를 가진다 (매우 안좋음 ㅠ)

 

3. Solving Recurrences  점화식 푸는 법 

점화식(Recurrence)는 재귀적 알고리즘의 시간 복잡도를 분석할 때 많이 쓴다. 

• T(n) → 크기 n짜리 문제를 풀 때 걸리는 시간
• T(n/2) → 크기 n/2 문제의 총 실행 시간
• T(1) → 크기 1짜리 문제를 풀 때 걸리는 시간 (보통 상수 시간 O(1)

 

점화식을 푸는 방법은 Substitution, Recurrence Tree, Master Theorem 이렇게 3가지가 있다.

 

Substitution: Guess a solution, replace with representative function, recurrence holds true

치환법은 점화식의 해답를 추측하고, 대표 함수로 대체하여 점화식이 성립함을 증명하는 방법이다.

점화식에서 최종 빅오 표현을 추측한 뒤, 수학적 귀납법 같은 방식으로 그 추측이 맞음을 증명하는 방법

 

Recurrence Tree: Draw a tree representing the recursive calls and sum computation at nodes

점화식 트리법은 재귀 호출을 나무 형태로 그려 각 노드에서의 계산을 합산하여 점화식의 해를 구하는 방법이다.

 

Master Theorem: A formula to solve many recurrences (R03)

마스터 정리는 여러 점화식을 간단한 공식으로 풀 수 있게 해주는 수학적 방법이다. (참고: R03)

 

 

4. Sort 종류 

4-1. Selection Sort (선택 정렬)

리스트에서 가장 작은(또는 큰) 값을 골라서 제자리에 가져다 놓는 정렬 알고리즘이다. 

이걸 반복해서 전체를 정렬한다.

 

Find a largest number in prefix A[:i + 1] and swap it to A[i]

A의 처음부터 i번째까지(prefix A[:i + 1]) 중에서 가장 큰 숫자를 찾아서 A[i] 위치로 교환하다.

 

* A[:i + 1] → 파이썬(Python) 같은 언어에서 쓰는 슬라이싱(slicing) 표현

A라는 리스트(배열)에서 A[0]부터 A[i]까지 (포함) 잘라낸 부분 

A = [1, 2, 3, 4]
i = 2
print(A[:i + 1])  # A[:3] → A[0], A[1], A[2]

→ [1, 2, 3]

 

Recursively sort prefix A[:i]

i번째를 제외한 앞쪽 부분(A[:i])을 재귀적으로 정렬하다.

 

Example:

[8, 2, 4, 9, 3], 처음 배열 [8, 2, 4, 9, 3]에서 시작한다

→[8, 2, 4, 3, 9], 가장 큰 값 9를 찾아 마지막으로 보내 [8, 2, 4, 3, 9]로 만들다.

→[3, 2, 4, 8, 9], 그다음 남은 부분 [8, 2, 4, 3]에서 가장 큰 값 8을 찾아 앞으로 옮겨 [3, 2, 4, 8, 9]로 만들다.

→[3, 2, 4, 8, 9], 다시 [3, 2, 4]에서 4를 찾아 뒤로 옮겨 [3, 2, 4, 8, 9]로 만든다.

→[2, 3, 4, 8, 9] 마지막으로 [3, 2]에서 2를 찾아 앞으로 옮겨 [2, 3, 4, 8, 9]로 만든다.

 

1 def selection_sort(A, i = None):          # T(i) selection sort 함수
2     '''Sort A[:i + 1]'''                 
3     if i is None: i = len(A) - 1          # O(1)   i가 None이면 배열 끝, i를 남은 갯수만큼 초기화 
4     if i > 0:                             # O(1)   i > 0이면 재귀 계속
5         j = prefix_max(A, i)              # S(i)   A[:i+1]에서 최대값 인덱스 찾기
6         A[i], A[j] = A[j], A[i]           # O(1)   최대값을 A[i]로 swap
7         selection_sort(A, i - 1)          # T(i-1) i-1 구간에 대해 재귀 호출

 

 

1 def prefix_max(A, i):                     # prefix_max 함수, A[:i+1] 최대값 인덱스 반환
2    '''Return index of maximum in A[:i + 1]'''  
3    if i > 0:                             # O(1)   i > 0이면 재귀 계속
4        j = prefix_max(A, i - 1)          # S(i-1) A[:i]에서 최대값 인덱스 찾기
5        if A[i] < A[j]:                   # O(1)   A[i] < A[j]이면
6            return j                      # O(1)   j 반환 (이전 최대값 유지)
7    return i                              # O(1)   아니면 i 반환 (현재 값이 최대)

• T(i) → selection_sort 함수의 시간복잡도 → i 까지 정렬하는 데 걸리는 시간
• S(i) → prefix_max 함수의 시간복잡도 → i 까지 최대값 인덱스를 찾는 데 걸리는 시간

 

prefix_max analysis 

prefix_max 함수에 대한 시간복잡도와 동작 원리를 분석

 

– Base case: for i = 0, array has one element, so index of max is i
 i=0일 때, 배열에 원소가 하나밖에 없으므로 최대값의 인덱스는 i이고 종료 

* Base case: 더 이상 쪼갤 수 없거나 재귀를 멈추는 조건(종료 조건)을 기술

 

– Induction: assume correct for i, maximum is either the maximum of A[:i] or A[i],

returns correct index in either case.
i에 대해 최대값 인덱스를 올바르게 반환한다고 가정하면,
A[:i] 구간의 최대값과 A[i] 중 더 큰 쪽을 비교해서 최대값 인덱스를 반환하면 된다.
따라서 두 경우 모두 올바른 인덱스를 반환하게 된다.

 

– S(1) = Θ(1),  S(n) = S(n − 1) + Θ(1)

 

∗ Substitution: S(n) = Θ(n), cn = Θ(1) + c(n − 1) ⇒ 1 = Θ(1) 

점화식을 풀어보면,

• S(n) = Θ(1) + Θ(1) + Θ(1) + … (n번 반복) = Θ(n).
  즉, 각 단계마다 상수 시간씩 더해지므로 전체는 선형 시간 Θ(n)이 된다.
  식에서 cn = Θ(1) + c(n − 1) 꼴로 나타내고,
  상수만큼 반복되니 마지막엔 1 = Θ(1)이 된다.

∗ Recurrence tree: chain of n nodes with Θ(1) work per node, 

각 노드의 합은

→ 점화트리(recursion tree)로 보면, n개의 노드(재귀 호출) 각각이 Θ(1)만큼 일한다.

 

selection sort analysis:

– Base case: for i = 0, array has one element so is sorted
i = 0일 때, 배열에 하나의 원소만 있으므로 정렬된 상태라 하다.

 

– Induction: assume correct for i, last number of a sorted output is a largest number of the array, and the algorithm puts one there; then A[:i] is sorted by induction
i가 올바르게 동작한다고 가정하고, 정렬된 출력에서 마지막 숫자는 배열의 최대값이어야 하고, 알고리즘은 그 최대값을 맨 뒤에 둔다
그러면 A[:i] 부분은 귀납적으로 정렬되다.

 

T(1) = Θ(1), T(n) = T(n − 1) + Θ(n)

∗ Substitution: T(n) = Θ(n²), cn² = Θ(n) + c(n − 1)² ⇒ c(2n − 1) = Θ(n)
→ 대입(substitution) 방법으로 풀음
T(n)은 Θ(n²)가 되며,
점화식을 cn² = Θ(n) + c(n−1)²로 풀어보면,
최종적으로 c(2n−1)은 Θ(n)이 된다

 

* Recurrence tree: chain of n nodes with Θ(i) work per node, ∑(i=0 to n−1) i = Θ(n²)

점화트리(recursion tree)로 보면, n개의 노드(재귀 호출)가 있고,
각 노드 i에서 Θ(i)만큼 일하고, 총 합은 

 

4-2. Insertion Sort 삽입 정렬 

Recursively sort prefix A[:i]

배열 A의 접두 부분 A[:i]를 재귀적으로 정렬한다

 

Sort prefix A[:i + 1] assuming that prefix A[:i] is sorted by repeated swaps

접두 부분 A[:i]가 이미 정렬되었다고 가정하고, A[:i + 1]을 반복적인 swap으로 정렬하다

 

Example:

[8, 2, 4, 9, 3] → 처음 배열
[2, 8, 4, 9, 3] → 2 와 8 비교 swap
[2, 4, 8, 9, 3] → 4 와 8 비교 swap

[2, 4, 8, 9, 3] → 8 과 9 비교. 이미 정렬되어 있어 그대로 둠

[2, 4, 8, 9, 3] → 3 와 9 비교 swap

[2, 4, 8, 3, 9] → 3 와 8 비교 swap

[2, 4, 3, 8, 9] → 4 와 3 비교 swap

[2, 3, 4, 8, 9] → 2 와 3 비교 이미 정렬되어 있어 그대로 둠

def insertion_sort(A, i = None):      # T(i)
    ’’’Sort A[:i + 1]’’’              # 주어진 배열 A의 0 ~ i까지 정렬하다
    if i is None: i = len(A) - 1      # O(1) → i가 None이면 배열 끝 인덱스로 설정하다
    if i > 0:                         # O(1) → i가 0보다 크면 (정렬할 요소가 남아있으면)
        insertion_sort(A, i - 1)      # T(i - 1) → i-1까지 재귀적으로 정렬하다
        insert_last(A, i)             # S(i) → i번째 요소를 적절한 위치로 넣다

def insert_last(A, i):                # S(i)
    ’’’Sort A[:i + 1] assuming sorted A[:i]’’’ # A[:i]는 이미 정렬되었다고 가정하고,
                                      # A[i]를 적절한 위치로 넣다
    if i > 0 and A[i] < A[i - 1]:     # O(1) → 현재 A[i]가 왼쪽 값보다 작으면
        A[i], A[i - 1] = A[i - 1], A[i]  # O(1) → swap하다
        insert_last(A, i - 1)         # S(i - 1) → 왼쪽으로 계속 확인하며 swap하다

 

insert_last analysis:

Base case: for i = 0, array has one element so is sorted

i = 0일 때, 배열에는 원소가 하나뿐이므로 이미 정렬된 상태다.

 

Induction: assume correct for i, if A[i] >= A[i - 1], array is sorted; otherwise, swapping last two elements allows us to sort A[:i] by induction

i 가 올바르다고 가정하면,  

• 만약 A[i] ≥ A[i-1]이면 배열은 정렬된 상태다.
• 그렇지 않다면, 마지막 두 원소(A[i], A[i-1])를 swap함으로써 A[:i] 구간은 귀납적으로 정렬할 수 있다.

 

– S(1) = Θ(1), S(n) = S(n − 1) + Θ(1) =⇒ S(n) = Θ(n)

 

• S(1) = Θ(1) → 원소 1개일 때는 상수 시간.
• S(n) = S(n−1) + Θ(1) → n개일 때는 n−1개를 정렬한 시간 + 상수 작업.
• 결론적으로 S(n) = Θ(n) → 전체는 선형 시간에 걸쳐 동작한다.

 

 

sertion_sort analysis:

– Base case: for i = 0, array has one element so is sorted

i = 0일 때, 배열에는 원소가 하나뿐이므로 이미 정렬된 상태다.

 

– Induction: assume correct for i, algorithm sorts A[:i] by induction, and then insert last correctly sorts the rest as proved above

i 가 올바르다고 가정하면,
알고리즘은 A[:i]를 귀납적으로 정렬하고,
그다음 insert_last 함수가 마지막 원소를 올바른 위치에 넣으므로 전체 A[:i + 1]도 올바르게 정렬된다

(앞에서 insert_last의 정당성이 이미 증명됨)

 

– T(1) = Θ(1), T(n) = T(n − 1) + Θ(n) =⇒ T(n) = Θ(n²)

 

• T(1) = Θ(1) → 원소 1개는 상수 시간에 정렬됨.
• T(n) = T(n−1) + Θ(n) → n개를 정렬하는 데 걸리는 시간은 n−1개를 정렬한 시간 + 마지막 원소를 올바른 위치에 넣는 데 드는 시간.
• 결론적으로 점화식을 풀면 T(n) = Θ(n²), 즉 이중 반복문 구조처럼 전체 시간 복잡도가 quadratic(제곱)이다.

 

 

4-3. Merge Sort 

Recursively sort first half and second half (may assume power of two)

배열의 첫 절반과 두 번째 절반을 재귀적으로 정렬하다.

(편의상 배열 길이가 2의 거듭제곱이라고 가정할 수 있다.)

 

Merge sorted halves into one sorted list (two finger algorithm)

정렬된 절반들을 하나의 정렬된 리스트로 합친다.
이때 two-finger 알고리즘(각 절반에 손가락 하나씩 두고 작은 값을 골라 합치는 방식)을 사용하다.

 

Example:

[7, 1, 5, 6, 2, 4, 9, 3], 시작 배열 

[7, 1, 5, 6],  [2, 4, 9, 3] 절반으로 나누기 

[7, 1], [5, 6], [2, 4], [9, 3] 또 절반 나누기 

[1, 7], [5, 6], [2, 4], [3, 9] 각 정렬 

 

[1, 7], [5, 6] 1과 5 비교 1 넣음 [1]. 왼손 손가락 → 7로 이동

[1, 7], [5, 6] 7과 5 비교 5 넣음 [1, 5] 오른손 손가락 → 6로 이동

[1, 7], [5, 6] 7과 6 비교 6 넣음 [1, 5, 6] 오른손 손가락 → 끝(더 이상 비교할 값 없음)

[1, 5, 6, 7] 왼손 리스트에 남은 값 7을 그대로 결과에 붙임

 

[2, 4, 9, 3]도 같은 방식으로 정렬 

결과 [1, 2, 4, 5, 6, 7, 9] 

 

1  def merge_sort(A, a = 0, b = None):                 # T(b - a = n)
2      ’’’Sort A[a:b]’’’
3      if b is None: b = len(A)                        # O(1)
4      if 1 < b - a:                                   # O(1)
5          c = (a + b + 1) // 2                       # O(1)
6          merge_sort(A, a, c)                        # T(n / 2)
7          merge_sort(A, c, b)                        # T(n / 2)
8          L, R = A[a:c], A[c:b]                      # O(n)
9          merge(L, R, A, len(L), len(R), a, b)      # S(n)

10 def merge(L, R, A, i, j, a, b):                    # S(b - a = n)
11     ’’’Merge sorted L[:i] and R[:j] into A[a:b]’’’
12     if a < b:                                      # O(1)
13         if (j <= 0) or (i > 0 and L[i - 1] > R[j - 1]): # O(1)
14             A[b - 1] = L[i - 1]                    # O(1)
15             i = i - 1                              # O(1)
16         else:                                      # O(1)
17             A[b - 1] = R[j - 1]                   # O(1)
18             j = j - 1                              # O(1)
19         merge(L, R, A, i, j, a, b - 1)            # S(n - 1)

 

merge analysis

– Base case: for n = 0, arrays are empty, so vacuously correct
n = 0일 때, 배열들이 비어 있으므로 당연히 참인 상태라서 base case로서 성립하다.

 

- Induction: assume correct for n, item in A[r] must be a largest number from remaining prefixes of L and R, and since they are sorted, taking largest of last items suffices; remainder is merged by induction
귀납 단계에서는 n에서 올바르게 동작한다고 가정하다.
A[r]에 들어갈 항목은 남은 L과 R 접두부 중에서 가장 큰 값이어야 하고, L과 R은 정렬되어 있으므로 각 마지막 값 중 큰 값을 선택하면 충분하다. 남은 부분은 귀납 가정에 의해 올바르게 merge되다.

 

– S(0) = Θ(1), S(n) = S(n − 1) + Θ(1) ⇒ S(n) = Θ(n)
S(0)는 비어 있는 배열이므로 Θ(1)이다. 
S(n)은 하나 줄인 경우(S(n-1))에서 한 번 추가 연산(Θ(1))이 더해지므로, 전체는 S(n) = Θ(n)으로 귀결되다.

 

merge sort analysis

– Base case: for n = 1, array has one element so is sorted
n = 1일 때, 배열에 원소가 하나뿐이므로 이미 정렬된 상태라서 base case로 성립하다.

 

– Induction: assume correct for k < n, algorithm sorts smaller halves by induction,

and then merge merges into a sorted array as proved above.
귀납 단계에서는 k < n일 때 올바르게 작동한다고 가정한다.
알고리즘은 작은 절반들을 귀납적으로 정렬하고, 앞에서 증명한 merge 단계가 이 절반들을 하나의 정렬된 배열로 합치므로 전체가 올바르게 정렬되다.

 

– T(1) = Θ(1), T(n) = 2T(n/2) + Θ(n)
T(1)은 원소 하나 처리니까 Θ(1)이다.
T(n)은 절반 크기의 문제 두 개를 풀고, 병합(merge)에서 Θ(n)만큼 추가 연산이 들어가므로 T(n) = 2T(n/2) + Θ(n)이라 나타내다.

 

∗ Substitution: Guess T(n) = Θ(n log n)
Substitution 방법에서는 T(n)을 Θ(n log n)이라 가정하다.

 

cn log n = Θ(n) + 2c(n/2)log(n/2) ⇒ cn log(2) = Θ(n)
수식을 대입하면 cn log n = Θ(n) + 2c(n/2)(log(n) − 1)로 전개되고,

이를 정리하면 cn log(2) = Θ(n)으로 귀결되다.

 

∗ Recurrence Tree: complete binary tree with depth log₂ n and n leaves,

level i has 2ᶦ nodes with O(n / 2ᶦ) work each, total: ∑(i = 0 to log₂n) (2ᶦ)(n / 2ᶦ) = ∑(i = 0 to log₂n) n = Θ(n log n)
Recurrence Tree 방법에서는 깊이 log₂n인 완전 이진 트리로 해석하다.
각 레벨 i에는 2ᶦ개의 노드가 있고 각 노드에서 O(n / 2ᶦ)만큼 연산을 수행하므로, 각 레벨 총합은 O(n)이다.
이걸 log₂n 레벨까지 모두 합하면 ∑(i = 0 to log₂n) n = Θ(n log n)로 최종 정리되다.

 

---

출처 

자료 https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec3/

강의 https://youtu.be/oS9aPzUNG-s?si=z8tydftAmSpLGlV_