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

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

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

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

1.1. Factorial

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)의 공간 복잡도를 갖는다는 것을 추정할 수 있다.

1.2. 피보나치 수열

f(0) = 1
f(1) = 1
f(n) = f(n - 1) + f(n - 2)
[Function 2] 피보나치 수열

2. 참조