팩토리얼 함수

팩토리얼 (factorial)

팩토리얼 ! 이란 양의 정수 n 이 있을 때 1부터 n까지의 자연수를 모두 곱한 값이다.

순환

정의

소스코드

def factorial(n):
    if n <= 1:
        return 1
    else:
        return n*factorial(n-1)

시간복잡도

소스코드를 시간에 대한 점화식 T(n) 으로 나타내보았다.

조건

상수 c 는 if 문 조건에서의 비교연산, else 문 return 에서의 곱셈연산 수행시간을 더한 값이다.

T(1) 의 값은 if 문의 비교연산이 한번만 진행된 값이므로 n 에 어떤 다른 값이 들어오던간에 상수 c 보다 작거나 같다고 할 수 있다.

계산

n 값이 0에 이를 때 까지 재귀를 진행한 후 위의 조건에 따라 T(1) 을 치환하면 cn 이라는 값을 얻어낼 수 있고 빅오 표기법으로 나타내면 O(n) 이라는 복잡도를 얻어낼 수 있다.

반복

소스코드

def factorial(n):
    sum = 1
    for i in range(1, n+1):
        sum *= i
    return sum

시간복잡도

정리

순환과 반복 모두 시간복잡도는 O(n) 으로 동일하지만 여러번 함수를 호출하는 순환적인 방법은 시간적, 공간적 측면에서 반복적인 방법보다 효율적이지 못하다.

그러나 이해가 쉽고 간결하게 프로그래밍 할 수 있다는 장점이 있어 순환으로 작성하는 것이 바람직하다고 한다.