여러 알고리즘 시간복잡도_재귀의 시간복잡도가 O(2^n)인 이유

Big - O는 알고리즘 성능을 예측한다. 

작은 차수는 무시하고 계수도 무시한다.

 

 

 

이진탐색 : O(logn)

재귀 : O(2^n)

정렬 : O(nlogn)

heap : 

- 생성 : nlogn

- push, pop : log(n)

 

 

---

 

여기서 궁금했던 것은 

왜 재귀가 2^n 인지이다.

 

재귀 중 피보나치를 생각했을 때 

 

이렇게 생각하면 된다.

T(n) > 2 * T(n-2)

T(n) > 2^2 * T(n-4) 

...

T(0)이 되면 

T(n) > 2^(n/2) * T(0) 이다.

T(0)은 계수가 되어 의미가 없어지고 1/2도 의미가 없어진다.

 

즉 재귀의 시간복잡도는 O(2^n)이 된다.