재귀 알고리즘 시간/공간 복잡도

재귀 알고리즘의 시간복잡도, 공간복잡도 계산법을 정리한다.

1. 재귀 알고리즘 시간 복잡도/공간 복잡도

f(0) = 1
f(n) = n * f(n - 1)

[Function 1] Factorial

T(n) = T(n - 1) + 1C
     = T(n - 2) + 2C
     = T(0) + nC
     = 1 + nC
     = O(n)

[Explanation 1] Factorial 시간 복잡도

시간 복잡도
- O(n)
- 함수 호출이 n번 발생하고 함수 내부적으로는 곱셈 연산을 제외한 별도의 연산이 수행되지 않기 때문에, 대략적으로 O(n)의 시간 복잡도를 갖는다는 것을 추정할 수 있다.
공간 복잡도
- O(n)
- 함수 호출이 n번 발생하고 함수 내부적으로도 함수 호출을 위한 Memory 사용량 이외에 별도의 Memory를 이용하지 않기 때문에, 대략적으로 O(n)의 공간 복잡도를 갖는다는 것을 추정할 수 있다.

f(0) = 1
f(1) = 1
f(n) = f(n - 1) + f(n - 2)

[Function 2] 피보나치 수열