[Java]거듭 제곱의 계산

*거듭 제곱의 계산

-> 거듭 제곱을 구현하는 방법은 간단하다. 기본적으로는 그 정의 그대로 어떤 수를 n번 곱하여 거듭제곱을 구현 가능하다. 하지만 n번 곱하기 때문에 시간복잡도는 O(n)이 걸린다는 것을 알 수 있다.

거듭제곱의 정의를 이용한 거듭 제곱

 

*개선된 거듭 제곱의 계산

-> 이러한 거듭 제곱은 분할 정복을 기반으로 시간복잡도를 O(logN)까지 줄일 수 있다!

-> 기본적인 아이디어는 다음과 같다. 예를 들어 5^10을 계산한다고 생각하였을 때, 아래와 같은 과정을 거쳐서 그 값을 구하는 것 이다.

거듭 제곱을 반으로 나눠, 한 값을 구하고 거듭 제곱이 짝수냐, 홀수냐에 따라 다르게 합치는 방식

-> 따라서, 재귀를 이용하여 다음과 같은 거듭제곱을 구현할 수 있음을 알 수 있다.

거듭 제곱 계산

 

*구현

-> 점화식도 구하였으니 그대로 구현하기만 해주면 된다.

import java.util.Scanner;

public class Exponentiation {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextInt(); // 밑
		long b = sc.nextInt(); // 지수

		System.out.println(pow(a, b));
		sc.close();
	}

	private static long pow(long a, long b) {
		// 지수가 0인 경우(종료 조건).
		if (b == 0) {
			return 1;
		}

		// 반으로 나눈 거듭제곱 계산.
		long res = pow(a, b / 2);

		// 지수가 짝수인 경우.
		if (b % 2 == 0) {
			return res * res;
		}
		// 지수가 홀수인 경우
		else {
			return res * res * a;
		}
	}
}