거듭제곱의 표현과 최적화

일반적인 거듭제곱 표현 O(N)

int func(int x, int n)
{
	int res = 1;
	for (int i = 0; i < n; i++)
		res *= x;
	return res;
}

장점: 작성이 쉽고 직관적임

시간복잡도 : 지수(n)만큼 계산하므로 O(N)

최적화 기법(분할 정복+재귀) : O(logN)

아이디어

짝수일 때 : 2의 8승을 2의 제곱을 구한다음 그것만 3번 곱해볼까?

홀수일 때 : 2의 7승을 2의6승을 짝수처럼 계산하고 거기다가 2를 곱해볼까?

시간복잡도: 지수를 반으로 나눠가며 계산하므로 O(logN) 

코드

#include<iostream>
using namespace std;
long long func(int x, int n);
int main()
{
	//2의 50승 구하기
	int x = 2;
	int n = 50;
	cout << "2의 50승은 " << endl;
	cout<<func(x, n) << "입니다." << endl;
}
long long func(int x, int n)
{
	if (x == 1)
		return 1;
	if (n == 1)
		return x;
	//지수가 홀수 일때 
	if (n % 2 == 1)
	{
		long long res = func(x, (n - 1) / 2);
		return (res * res) * x;
	}
	//지수가 짝수 일 때
	else
	{
		long long res = func(x, n / 2);
		return res * res;
	}
}

결과