[4. 기본자료형] 4.7 power계산하기

---

Q 4.7 power계산하기

double x 와 int y 가 주어졌을때 x^y를 계산하라.(오버플로우는 무시해도 좋다.)

---

가장 먼저 생각하는 방법은 x를 y-1번 곱하는 방법이다. 이 방식은 시간 복잡도가 O(n²)이 된다.
따라서 조금더 효율적으로 만들기 위해서는 전체 곱셈 횟수를 줄여야 한다.
지수의 특징을 사용해서 y의 최하위 비트가 0이라면 (x^(y/2))² 의 결과와 같은 값이 나온다.
y의 최하위 비트가 1이라면 x dot (x^(y/2))²의 결과와 같은 값이 나온다.

해당 코드와 코딩결과는 다음과 같다.

시간복잡도 O(n)