[수학][제곱] a^n 제곱

[수학][제곱] a^n 제곱

a의 n제곱 빠르게 구하기

1. 단순 반복문     -> 시간 복잡도 O(n)

int ans = 1;
for(int i = 1; i <= n; i++)    {
    ans *= i;
}

2. 분할 정복

     

int times(int a, int n)
{
    int temp;
    if(n == 0)    return 1;
    if(n == 1)    return n;
    if(n % 2)     return a * times(a, n - 1);
    
    // n % 2 == 0
    temp = times(a, n / 2);
    return temp * temp;
}

 * n이 짝수일 때 

return times(a, n / 2) * times(a, n / 2);

를 할 경우 (중복되는) 함수 호출이 2배가 되어 시간복잡도는 O(2^n)이 된다.

3. 이진수 이용하기

>> n의 이진수 중 1에 해당할 때 곱하여 나간다.

int times(int a, int n)
{
    int ans = 1;
    while(n > 0)        {
        if(n % 2)    
            ans *= a;
        a *= a;
        n /= 2;
    }
    return ans;
}

>> a는 반복문을 돌 때마다 (이진수의 자리수를 옮길 때 마다)

a *= a를 통해서 제곱을 해 준다.

관련 문제

https://www.acmicpc.net/problem/1629