알고리즘
시간 복잡도 개념
도그rin
2023. 4. 26. 20:10
⏲ 빅오 표기법
- 가장 빠르게 증가하는 항만 고려하는 표기법
- 함수의 상한을 나타냄
- 차수가 가장 큰 항에서 계수를 제외하여 표현
- 예시) 4*N^3 + 2*N^2 + 100인 알고리즘이 있다면, O(N^3)으로 표현
| 시간 복잡도 좋음 | |
| O(1) | 상수 시간 |
| O(logN) | 로그 시간 |
| O(N) | 선형 시간 |
| O(NlogN) | 로그 선형 시간 |
| O(N^2) | 이차 시간 |
| O(N^3) | 삼차 시간 |
| O(2^n) | 지수 시간 |
| 시간 복잡도 나쁨 | |