팩토리얼 (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) 으로 동일하지만 여러번 함수를 호출하는 순환적인 방법은 시간적, 공간적 측면에서 반복적인 방법보다 효율적이지 못하다.
그러나 이해가 쉽고 간결하게 프로그래밍 할 수 있다는 장점이 있어 순환으로 작성하는 것이 바람직하다고 한다.
댓글