728x90
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)이 된다.
반응형
'알고리즘 > 알고리즘 개념' 카테고리의 다른 글
| [Python]Permutation을 아십니까? (0) | 2023.10.29 |
|---|---|
| [Python]다익스트라_최단경로알고리즘 (feat. heap) (0) | 2022.09.22 |
| [python]유니온파인드 알고리즘_이것도 알아야해? (0) | 2022.08.24 |
| 비트마스크? 그게 뭔데 (0) | 2022.08.11 |
| [python]이차원 배열을 뒤집는 방법_zip(*list) (0) | 2022.08.03 |