분할정복을 이용한 거듭제곱

어떤 수의 제곱은 해당 수를 두 번을 곱함으로써 구할 수 있다. 이는 제곱식의 지수가 커지더라도 같으며 커지면 지수가 커지면 커질 수록 시간이 오래 걸린다. 예를 들어, 11의 12 제곱은 다음과 같이 구할 수 있다. int result = 1; for (int i = 0; i < 12; i++) { result *= 11; } System.out.println(result); 위와 같은 식에서 지수가 한없이 커진다면 해당하는 시간 만큼 반복문이 돌아야 하기 때문에 시간 복잡도는 O(N)이 걸린다. 위의 식을 더 빠르게 계산할 수는 없을까? 분할정복을 이용한 거듭제곱은 위에 대한 해결 방식이다. 예를 들어 11의 12 제곱은 11의 6제곱과 11의 6제곱의 곱을 통하여 구할 수 있는데 이처럼 분할하여 계..