[알고리즘]분할과 정복 개념 및 예시

분할과 정복

• 큰 입력의 문제를 작은 입력의 문제들로 나눈다.
• 나눈 작은 문제들의 해를 재귀적으로 구현한다.
• 재귀적으로 나눈 문제들의 해를 이용하여 원래 문제의 해를 구한다.

리스트(배열)에서 최대값 찾기

분할과 정복

Algorithm maximum(a, first, last)
    if(first == last) then
        return a[first]
    else
        mid = (first + last) // 2
        lmax = maximum(a, first, mid)
        rmax = maximum(a, mid + 1, last)
        if lmax > rmax then
            return lmax
        else
            return rmax

• mid 를 기준으로 나눈 왼쪽 반의 최대값 lmax 와 오른쪽 반의 최대값 rmax 를 비교하여 더 큰값이 전체 최대값이다.

수행시간분석

T(n) : maximum(a, 0, n-1)의 수행시간 (원소비교회수)

• n = 2k일 경우
• T(n) = 0 (n = 1 경우)

​ = 2T(n/2) + 1 (n > 1 경우)

T(n) = O(n)

• 일반적인 n에 대하여
• T(n) = 0 (n = 1 경우)

​ = 2T(n/2) + 1 (n > 1 경우)

T(n) = O(n)