ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 팩토리얼 (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) 입니다. 순환적인 방법과 시간복잡도가 같습니다.

    '자료구조(Data Structure)' 카테고리의 다른 글

    팩토리얼 (Factorial)  (0) 2020.10.21

    댓글 0

Designed by Tistory.