순환-거듭제곱 계산

순환을 사용하지 않고 x의 n제곱 값을 구하는 함수 작성

double slow_power(double x, int n) {
	int i;
	double result = 1.0;

	for (i = 0; i < n; i++)
		result = result * x;
	return(result);
}

- 루프 1회당 한 번의 곱셈이 필요하고 루프의 횟수는 n회

- O(n)의 시간복잡도

 

순환을 사용하여 x의 n제곱 값을 구하는 함수 작성

 

1. 알고리즘

power(x, n) : if(n==0) return 1; else if(n==짝수) return power(x^2, n/2); else if(n==홀수) return x*power(x^2, (n-1)/2);

- x^n=(x^2)^(n/2)이므로

double power(double x, int n) {
	if (n == 0) return(1);
	else if ((n % 2) == 0)
		return(power(x * x, n / 2));
	else if ((n % 2) == 1)
		return(power(x * x, (n - 1) / 2));
}

- 한 번의 순환 호출을 할 때마다 문제의 크기는 약 절반으로 감소

- n을 2^k라 가정한다면 순환 호출 한 번 당 n의 크기가 절반씩 줄어듦

- 2^k부터 2^0까지 약 k번의 순환 호출 발생

- 한 번 호출될 때마다 곱셈과 나눗셈이 각각 약 1번씩 발생하므로 전체 연산의 개수는 k=log2n에 비례

- O(logn)의 시간 복잡도