팩토리얼 계산

 

 

공부했던 자료 정리하는 용도입니다.

재배포, 수정하지 마세요.

 

 

---

팩토리얼(거듭제곱 값) 계산

  반복적인 방법이 순환적인 방법에 비하여 속도가 더 빠르다.

 

---

 

1. 반복문을 사용하는 방법

double power_1(double x, int n)
{
	int i;
	double result = 1.0;
	
	for (i = 0; i < n ; i++)
		result *= x;
	return (result);
}

한 번의 루프마다 한 번의 곱셈이 일어나므로 시간 복잡도는 $O(n)$이 된다.

 

 

 

2. 순환을 사용하는 방법

double power_2(double x, int n)
{
	if (n == 0)
		return 1;
	else if ((n % 2) == 0)	// n이 짝수인 경우
		return power_2((x * x), (n / 2));
	else	// (n % 2) != 0 -> n이 홀수인 경우 
		return x * power_2((x * x), ((n - 1) / 2));
}

$x^n = (x^2)^{\frac{n}{2}}$ 의 공식을 이용하는 방법이다.

n이 짝수인 경우에는 $x^2$을 먼저 계산한 후에 이 값을 $\frac {n}{2}$제곱하고,

n이 홀수인 경우에는 $x^2$을 $\frac{n-1}{2}$제곱한 뒤 $x$를 한번 더 곱해야 한다.

함수를 한번 호출할 때마다 n승, $\frac{n}{2}$, $\frac{n}{4}$승으로 점점 문제의 크기가 약 절반으로 줄어든다.

 

 

 

  시간 복잡도

$2^k$ → $2^{k-1}$ → $2^{k-2}$ → ... → $2^1$ → $2^0$

약 k번의 순환 호출이 일어난다. $n = 2^k$이므로 양변에 log를 취하면 $log_2n = k$가 된다.

한 번의 순환 호출이 일어날 때마다 약 1번의 곱셈과 1번의 나눗셈이 일어나므로 전체 연산의 개수는 $k = log_2n$에 비례하게 되어 시간 복잡도는 $O(log_2n)$이 된다.