[Recursion] Complexity analysis using factorial

 

Complexity analysis of recursive programs – using factorial

 

1.    Time Complexity

   -  the measurement of how the time taken by a program with the input

2.    Space Complexity

   -  the measurement of how the space or memory consumed by the program grows with input

 

 

n factorial을 계산하는데 걸리는 시간이 T(n)이라고 가정한다.

프로그램의 시간 복잡도를 분석하려고 할 때 각 작업은 1 unit의 시간이 소요된다고 가정한다.

 

 

시간복잡도(Time Complexity)

n이 0보다 큰 경우 먼저 0과 비교한다. (n==0)

이 작업은 1unit의 시간이 소요된다.

그 다음 Factorial(n-1)에서 리턴을 받은 값과의 곱셈에서 1unit, (n-1)뺄셈에서 1unit이 소요된다.

그러면 n>0 일 때, T(n)=T(n-1)+3의 식으로 표현할 수 있다.

n이 0일 때는 첫 번째 if문에서 n==0 비교만 하기 때문에 T(0)=1의 식이 된다.

 

이제 T(0)=1을 통해 T(n)=T(n-1)+3의 식을 간단한 식으로 표현해보자. 

T(n-1)=T(n-2)+3으로 나타낼 수 있고, 그러면 T(n)=T(n-2)+6으로 표현된다.

다시 T(n-2)=T(n-3)+3으로 나타낼 수 있고, T(n)=T(n-3)+9로 표현된다.

따라서 이 식을 k를 사용해서 간단하게 표현하면, T(n)=T(n-k)+3*k가 된다.

 

이 식을 T(0)으로 표현하기 위해서는 n-k=0, 즉 k=n이어야 한다.

따라서 T(n)=T(0)+3n이고, T(0)=1이기 때문에 T(n)=3n이다.

 

결과적으로 input n에 대한 프로그램에 대해 소요시간은 n에 정비례하는 것을 알 수 있으며,

이것을 O(n)으로 표기한다.

 

 

 

공간복잡도(Space Complexity)

또 다른 예시를 들기 위해 F(5)를 구한다고 하자. (Factorial을 줄여서 F로 표기)

F(5)는 F(4)를 재귀적으로 계산한다.

이 단계에서 컴퓨터는 F(5)함수를 메모리에 저장하고 F(4)를 먼저 계산한다.

그리고 F(4)의 계산이 끝나면 다시 F(5)에 돌아와 남은 계산을 하게 된다.

 

하지만 F(5)를 저장하고 F(4)를 계산하려니 F(3)가 재귀적으로 먼저 계산되고 F(4)도 메모리에 저장된다.

그렇게 F(0)가 호출되기까지 F(5), F(4), F(3), F(2), F(1)이 메모리에 저장되며 공간을 소요하게 된다.

이것을 암시적 스택이 메모리에 증가한다고 말한다.

 

그렇다면 이 스택의 최대 사이즈는 몇일까?

이 재귀 트리 구조에서는 최대 n의 깊이를 가진다.

(트리의 최대 깊이는 트리에서 가장 긴 경로를 의미한다.)

 

각 level로의 경로는 1 unit이고, L0에서 L5까지의 최대 경로는 5 units가 된다.

즉, F(5)의 경우 최대 깊이는 5이다.

다시 말해 이 프로그램 F(n)에 필요한 공간은 n units로 input n에 정비례하고, 공간복잡도는 O(n)이다.

이것은 공간복잡도 측면에서의 n차 알고리즘이다.

 

 

 

 

↓ 참고 사이트

https://www.youtube.com/watch?v=ncpTxqK35PI&list=PL2_aWCzGMAwLz3g66WrxFGSXvSsvyfzCO&index=3