문제

[코플릿 - power]

Math.pow를 사용하지 않고 거듭제곱을 구하는 문제이다.

간단하게 for문을 사용하여 문제를 해결할 수 있지만, 시간복잡도를 최대한 줄여보고자 한다.
시간복잡도를 O(log N)으로 만들기 위해서 분할정복을 이용한다.

• for문 사용 -> O(N)
• 분할정복 -> O(log N)

---

코드

O(N)

public long power(int base, int exponent) {
    long result = 1;
    for (int i = 0; i < exponent; i++) {
        result *= base;
    }
   return result;
}

O(log N) - 재귀 O

public long power(int base, int exponent) {
    if(exponent == 0) return 1;
    int half = exponent / 2;
    
    long temp = power(base, half);
    long result = (temp * temp);

    if(exponent % 2 == 1) return (base * result);
    else return result;
}

base = 3, exponent = 14 일때, O(N) 방식은 3을 14번 곱한다.

O(log N) 방식은 temp를 제곱하여 시간 복잡도를 줄인다.

3¹⁴ = (3⁷)²
3⁷ = (3³)² x 3
3³ = (3¹)² x 3
3¹ = 1² x 3
3⁰ = 1

3¹⁴ = (((1 x 3)² x 3)² x 3)²

• 지수가 짝수이면, temp를 제곱한다.
• 지수가 홀수이면, temp를 제곱하고 base를 곱한다.

✔️ 재귀의 흐름

exponent = 14
-> exponent = 7
-> exponent = 3
-> exponent = 1
-> exponent = 0, return 값 = 1
-> exponent = 1 (홀수), temp = 1, return 값 = 3
-> exponent = 3 (홀수), temp = 3, result = (3)² * 3 = 3³
-> exponent = 7 (홀수), temp = 3³, result = (3³)² * 3 = 3⁷
-> exponent = 14 (짝수), temp = 3⁷, result = (3⁷)² = 3¹⁴

O(log N) - 재귀 X

public long power(int base, int exponent) {
     long result = 1;

     while (exponent > 0){
        if((exponent & 1) != 0){ 
          result *= base;
        }
        base *= base;
        exponent >>= 1;
     }
     return result;
}

재귀와 푸는 방식은 비슷하지만, while문을 사용하였다.

✔️ (exponent & 1) != 0
해당 조건문은 exponent가 홀수인지를 판별하는 코드이다.
exponent가 홀수이면 마지막 비트가 1이므로, & 연산자를 하면 항상 1이 된다.
exponent가 짝수이면 마지막 비트가 0이므로 항상 0이 된다.

ex)
11 & 1 = 1011 & 0001 = 0001(이진수) = 1(십진수)
12 & 1 = 1100 & 0001 = 0000(이진수) = 0(십진수)

✔️ exponent >>= 1
비트 연산자를 사용해서 exponent = exponent / 2를 해준다.
exponent >>= 1 대신에 exponent = exponent / 2로 작성해줘도 된다.

---

[참고]
https://rito15.github.io/posts/algorithm-pow/
https://torbjorn.tistory.com/361
비트연산 - & 연산
분할정복 거듭제곱
https://hbj0209.tistory.com/43