분할정복 이용 알고리즘

a^n을 계산하려고 할 때 a를 n번 곱하는 식으로 계산하면 O(n)의 시간이 걸린다. 하지만 분할 정복을 이용하면 O(logn)까지 시간을 단축할 수 있다.
n이 짝수일때 a^n = (a^n/2)^2
n이 짝수일때 a^n = (a^n/2)^2 * a
다음 점화식을 이용하여 해결할 수 있다.

public class Main
{ // a^n 구하기
    public static int pow(int a, int n)
    { // O(n)
        if (n == 0) return 1;
        return a * pow(a, n-1);
    }
    
    public static int powDC(int a, int n)
    { // O(logn)
        if (n == 0) return 1;
        int ans = powDC(a, n/2);
        if (n % 2 == 0) // n이 짝수인 경우
            return ans*ans;
        else // n이 홀수인 경우
            return ans*ans*a;
    }
    
    public static int powDC2(int a, int n)
    { // 분할 정복 비재귀
        int ans = 1;
        while (n > 0)
        {
            if (n%2 == 1) // n이 홀수인 경우 a 한번 더 곱함
                ans *= a;
            a *= a; // 홀,짝수에 상관없이 제곱시킴
            n /= 2;
        }
        return ans;
    }
    
    public static void main(String[] args)
    { 
        System.out.println(powDC(3, 4));
    }
}