[알고리즘] Divide and Conquer(분할정복)

Divide and Conquer

: 여러 알고리즘의 기본이 되는 해결 방법으로, 크고 방대한 문제를 작은 문제로 나눠가면서 풀고 합쳐서 해결하는 방식

-> 재귀적인 마인드로 문제를 해결하는 기법

-> sort, search

 

step1 : Divide

- 주어진 input을 small instance로 나눈다

 

step2 : Conquer

- smaller instance에 대한 solution

- 쉽게 solution을 구하지 못하면 recursive(divide된 conquer도 divide & conquer 반복)

 

step3 : Combine(If necessary)

- original instance의 해를 구할 수 있도록 smaller instance 이용

 

 

✔️ Merge Sort

: 원소 개수가 1 또는 0이 될 때까지 두 부분으로 쪼개고, 쪼개서 자른 순서의 역순으로 크기를 비교해 병합해 나가는 방식

 

step1 : Divide

- 주어진 input을 두 개의 subarrays로 나눈다.

 

step2 : Conquer

- 각각의 subarray가 충분히 작으면 정렬한다.

- divide & conquer을 반복(recursion)하여 정렬한다.

 

step3 : Combine(If necessary)

- 정렬된 subarrays를 하나의 배열로 merge한다.

 

 

다음 코드는 Swift로 작성한 함수이다.

func mergeSort(S:[Int])->[Int]{
    if S.count>1
    {
        let mid : Int = S.count/2
        
        var arr1 = [Int]()
        var arr2 = [Int]()
        
        arr1 = Array(S[0..<mid])
        arr2 = Array(S[mid..<S.count])
        
        let L = mergeSort(S: arr1)
        let R = mergeSort(S: arr2)
        return merge(L: L, R: R)
    }
    return S
}

func merge(L:[Int],R:[Int])->[Int]
{
    var result=[Int]()
    var left = L
    var right = R
    
    while(!left.isEmpty && !right.isEmpty)
    {
        let value = left[0] < right[0] ? left.removeFirst():right.removeFirst()
        result.append(value)
    }
    if !left.isEmpty
    {
        result+=left
    }
    if !right.isEmpty
    {
        result+=right
    }
    
    return result
}

 

👉 Best Case 시간 복잡도

시간 복잡도 = left 시간 + right 시간 + merge 시간

Merge의 Best Case 시간 복잡도

 

- Basic Operation : left[0]과 right[0]의 비교

left[0] < right[0]

- Input Size : L, R 각각의 배열의 item 수

 

: 배열이 모두 정렬된 상태

=> n/2

 

B(n) = B(n/2) + B(n/2) + n/2 = nlog₂n + n/2 ∈ θ(nlog₂n)

 

 

👉 Worst Case 시간 복잡도

시간 복잡도 = left 시간 + right 시간 + merge 시간

Merge의 Worst Case 시간 복잡도

: 배열 S의 모든 cell이 비교 후에 정렬될 때

=> n - 1

 

 

W(n) = W(n/2) + W(n/2) + n-1 = nlog₂n - (n - 1) ∈ θ(nlog₂n)