Binary Exponentiation 적용을 통한 시간 복잡도 O(n)에서 O(log n)으로 개선

Context

단순 반복문을 통한 거듭제곱 계산 방식의 비효율성 분석. 지수 n의 크기가 증가함에 따라 연산 횟수가 선형적으로 증가하는 O(n) 성능 한계 발생.

Technical Solution

• 지수를 2의 거듭제곱 형태로 분해하는 Binary Exponentiation 알고리즘 도입
• 지수가 짝수인 경우 x²ⁿ/₂ 공식을 적용하여 연산 횟수를 절반으로 단축하는 구조 설계
• 지수가 홀수인 경우 결과값에 x를 곱한 후 지수를 1 감소시켜 짝수 조건으로 전환하는 로직 구현
• 음수 지수 처리를 위해 x를 1/x로 치환하고 지수를 양수로 변환하는 전처리 단계 추가
• Integer.MIN_VALUE 처리 시 발생하는 Overflow 방지를 위해 지수 변수를 long 타입으로 캐스팅하여 안정성 확보