[Swift] Data Structure divide and conquer, D&C / power / 자료구조 분할정복 / 거듭제곱 계산

[분할정복]

[Swift] Data Structure recursion / divide and conquer, D&C / 자료구조 순환, 재귀 / 분할정복

 

 

x의 n승 거듭제곱을 하기 위한 함수를 작성하였다. recursion을 생각하지 않고 작성한다면 다음과 같이 작성할 것이다.

 

func slow_power(_ x: Double, _ n: Int) -> Double{
    var result = 1.0
    for i in 0..<n{
        result = result * x
    }
    return result
}

 

 

순환의 개념을 사용하여 효율적으로 거듭제곱을 구하는 함수를 작성해보자.

 

func fast_power(_ x: Double, _ n: Int) -> Double{
    
    if n == 0{
        return 1.0
    }
    else if n%2 == 0 { //n이 짝수
        return fast_power(x*x, n/2)
    }
    else{ //n이 홀수
        return x*fast_power(x*x, (n-1)/2)
    }
}

n이 짝수인 경우에 x 제곱을 먼저 계산한 후에 이 값을 n/2승 하는 것이다.

n이 홀수인 경우에 x 제곱을 (n-1)/2승하고 여기에 x를 곱해준다.

 

 

이 경우에는 n -> n/2 -> n/4 승이 되면서 함수가 1회 진행될 때마다 문제가 하나씩 줄어드는 게 아닌 절반씩 줄어든다. slow_power보다 매우 효율적이라고 할 수 있겠다.