POWER 알고리즘

문제

두 수를 입력받아 거듭제곱을 리턴해야 합니다.

제한사항

• Math.pow, 거듭제곱 연산자 사용은 금지됩니다.
• 시간복잡도 O(logN)을 만족해야 합니다.

풀이

O(logN)의 power 함수1

def power(a, n):
    ret = 1
    while n > 0:
        if n % 2 != 0:
            ret *= a
        a *= a
        n //= 2        
    
    return ret
    
print(power(5, 5))
print(power(5, 21))

5^21 = 5^1 x 5^4 x d^16임을 활용하여 계산하는 방법이다.

n을 제곱해나가면서 계산하므로 시간복잡도는 O(logN)이다.

O(logN)의 power 함수2

function power(base, exponent) {
  if (exponent === 0) return 1;

  const half = parseInt(exponent / 2);
  const temp = power(base, half);
  const result = temp * temp ;

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