[자료구조] 거듭제곱값 계산

이전 게시글과 유사하게 반복과 순환의 기법으로 프로그래밍할 것이다.

 

power 함수를 반복적으로 구현하면 다음과 같다.

int power(double x, int n) {
	double result = 1.0;
    	for (int i = 0; i<n; i++) {
    		result *= x; // x를 n만큼 곱한다.
    	}
      	return result;
}

 

 

순환으로 구현하면 다음과 같다.

int power(double x, int n) {
	if (n == 0) return;
    	else if (n % 2 == 0) // n이 짝수
    		return power(x^2, n/2);
    	else if (n % 2 != 0) // n이 홀수
    		return x*power(x^, (n-1)/2); 
 }

 

n이 짝수라면, (x^2)^(n/2) = x^n으로 계산할 수 있다.

n이 홀수라면, x * (x^2)^((n-1)/2) = x * x^(n-1) = x^n 이다.

 

 

 

반복적으로 구현한 함수의 시간복잡도가 O(n)이고, 순환적인 함수의 시간복잡도는 한 번 호출할 때마다 크기가 절반으로 줄어들기 때문에 O(logn)이다.

따라서 순환구조 함수가 실행 속도가 훨씬 빠르다.