-
팩토리얼 (Factorial)자료구조(Data Structure) 2020. 10. 21. 16:53
목차
1. 팩토리얼이란?
2. 순환을 이용한 팩토리얼
3. 반복을 이용한 팩토리얼
1. 팩토리얼이란?
특정 정수에서 1까지의 수를 모두 곱하는 것을 뜻합니다. 기호는 숫자 뒤에 느낌표인 !를 붙입니다.
예를 들어, 4! = 4 x 3 x 2 x 1 입니다. 즉, 4! = 24입니다.
마찬가지로 5! 는 5 x 4 x 3 x 2 x 1 = 120입니다.
2. 순환을 이용한 팩토리얼
위에서 말했듯이 팩토리얼은 다음과 같습니다.
4! = 4 x 3 x 2 x 1
5! = 5 x 4 x 3 x 2 x 1
위와같이 배치해보니 4! 에 5만 곱하면 5! 가 되는것을 알수 있습니다. 즉, 5! = 5 x 4! 가 되는 것입니다.
5를 임의의 수 n 으로 나타내보면 n! = n x (n-1)! 인 형태인 것을 볼수 있습니다.
즉 하나의 팩토리얼 함수를 순환적으로 호출하다보면 값이 나오는 것입니다.
#include <stdio.h> int factorial_recursive(int num) //recursive 는 '순환적인'이라는 뜻입니다. { if (num <= 1) return 1; // 1! = 1 return num * factorial_recursive(num-1); // n! = n * (n-1)! } int main() { //순환을 이용한 팩토리얼 printf("%d",factorial_recursive(4)); // 4! printf("\n"); // 줄 바꿈 printf("%d",factorial_recursive(5)); // 5! return 0; }
결과 :
24
120
[시간복잡도]
순환적인 팩토리얼을 점화식으로 나타내면 T(n) = T(n-1) + c 입니다. c 는 n 과 factorial_recursive(n-1) 를 곱하는 비용입니다.
순환을 수행할때마다 알고리즘이 수행해야할 크기가 n 에서 n-1 로 줄어드므로 시간복잡도는 O(n) 입니다.
3. 반복을 이용한 팩토리얼
#include <stdio.h> int factorial_iterative(int num) //iterative 는 '반복적인'이라는 뜻입니다. { if(num <= 1) return 1; // 0! = 1 이고 1! = 1 이기 때문에 인수가 1 이하이면 바로 1을 // 리턴해준다 int result = 1; //결과값을 나타낼 result for(int i = 2; i <= num; i++) //2부터 시작하여 num 이하까지의 수를 곱한다. result *= i; return result; //리턴 결과가 곧 num!이다 } int main() { //반복을 이용한 팩토리얼 printf("%d",factorial_iterative(4)); // 4! printf("\n"); // 줄 바꿈 printf("%d",factorial_iterative(5)); // 5! return 0; }
결과 :
24
120
[시간복잡도]
반복문이 n-1 번 반복하니 시간복잡도는 O(n) 입니다. 순환적인 방법과 시간복잡도가 같습니다.