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

설명

• 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘
• 퀵 정렬, 합병 정렬로 대표되는 정렬 알고리즘 문제와 고속 푸리에 변환 문제가 대표적

설계 전략

• 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눔
• 정복(Conquer) : 나눈 작은 문제를 각각 해결
• 통합(Combine) : (필요하다면) 해결된 해답을 모음

거듭 제곱 (Exponentiation)

• O(n)

# 반복문을 이용한 거듭제곱
def Iterative_Power(x, n):
    result = 1

    for i in range(1, n+1):
        result *=  x

    return result

 

• O(logn)

# 분할 정복을 이용한 거듭제곱
def Recursive_Power(x, n):
    if n == 1: return x
    if n % 2 == 0:
        y = Recursive_Power(x, n//2)
        return y * y
    else:
        y = Recursive_Power(x, (n-1)//2)
        return y * y * x