거듭제곱 시간복잡도 줄이기

거듭제곱이란

base^exponent의 형태인데

예를들어 2^50이면 2를 50번 곱하는것이며 반복되는 횟수는 50번이다

 

for문으로 나타낸다면

let result = 1
for(let i = 0 ; i < exponent; i++){
  result *= base 
}
console.log(result)

가 될것이며 result가 결과값이고 지수인 exponent만큼 반복을 한다

시간복잡도는 O(n)이 된다.

 

이것을 개선을 한다면

아까 2^50을 단순히 50번 반복을 하는것이 아니라

base *= base로 두면서 exponent /= 2로 두는것이다

즉, 예를들어 예시는 지수를 작게 10으로 두겠다

2^10

-> 4^5

-> 16^2 * 4

-> 256^1 * 4

이런 형식으로 지수를 반씩 줄이는 것이다.

 

코드는

function pow(base, exponent) {
  let mul = 1n;
  while (exponent > 1n) {
    if (exponent % 2n === 0n) {
      base *= base;
      exponent /= 2n;
    } else {
      mul *= base;
      base *= base;
      exponent /= 2n;
    }
  }
  return base * mul;
}

이며 mul은 지수가 홀수일때 그 당시의 base값들을 곱해 나간값이다

 

시간복잡도가 O(logn)이 된다

 

예를들어

2^500의 경우 8번반복

2^5000의 경우 12번 반복

2^50000의 경우 15번 반복

2^500000의 경우 18번 반복

2^5000000의 경우 22번 반복을 한다

지수가 커질수록 속도감소의 효과를 기하급수적으로 볼 수 있다.