[알고리즘] 거듭제곱

base와 exponent를 입력받아 거듭제곱을 리턴.
base가 밑, exponent가 지수라고 생각하면 된다.

base의 범위는 2보다 크거나 같고,
exponent는 0보다 크거나 같다.

number 타입을 리턴해야 하며, 실제 계산 결과를 94,906,249로 나눈 나머지를 리턴해야 한다고 함. 이렇게 나머지를 구하는 이유는 산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문이라고 한다. (이 과정은 연산 중간에 해주어야 함)

내가 쓴 코드

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

  return (base * power(base,exponent-1))%94906249
}

거듭제곱의 값을 구하는 데는 성공했지만, 시간복잡도를 줄이는 데는 실패했다.
탈출조건은 지수가 0이 될 때이며, 0이 아닐 때는 base에 재귀함수에 base와 exponent-1을 한 값이 들어가게 된다.

reference

function power(base, exponent) {
  if (exponent === 0) return 1;//탈출 조건은 동일 

// 효율성을 높이기 위해서 반으로 나누어 계산한다 (반 이후로는 계산하지 않을 수 있으니 시간복잡도 절약됨)
  const half = parseInt(exponent / 2);
  const temp = power(base, half);
  const result = (temp * temp) % 94906249;

// 반으로 완전히 나누어지지 않는 홀수의 경우에는 temp*temp를 한 뒤에 base를 한 번 더 곱해준다 
  if (exponent % 2 === 1) return (base * result) % 94906249;
  else return result;
}

시간 복잡도를 줄이기 위해서 래퍼런스에서는 주어진 exponent의 반만 계산을 실행해주도록 했다. 그 뒤로는 구한 temp값을 통해 temp 곱하기 temp를 하면 원래 구하고자 했던 값이 나오게 된다.

exponent가 홀수 일 때가 문제가 되는데, 이 경우에는 temp 곱하기 temp를 해준 뒤에 다시 base를 한 번 더 곱해주면 된다.

시간복잡도를 줄이기 위해서 보통 반만 계산하는 방법을 많이 사용하는 것 같다.

parseInt는 정수를 리턴하도록 하는 함수인데 여기서는 소수점을 제거해주는 용도로 쓰임.