정의
빅오 표기법의 시간복잡도 차이를 비교하기
시간 복잡도 순서
O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)
logN과 √N 비교
| N | √N | logN |
| 4 | 2 | 2 |
| 4^2 | 4 | 4 |
| 4^3 | 8 | 6 |
| 4^10 | 1024 | 20 |
| 4^20 | 1048576 | 40 |
초반에는 비슷하지만, N이 커질수록 logN은 √N보다 더 효율적이다
결론 : N < √N < logN
빅오 표기법의 시간복잡도 차이를 비교하기
O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)
| N | √N | logN |
| 4 | 2 | 2 |
| 4^2 | 4 | 4 |
| 4^3 | 8 | 6 |
| 4^10 | 1024 | 20 |
| 4^20 | 1048576 | 40 |
초반에는 비슷하지만, N이 커질수록 logN은 √N보다 더 효율적이다
결론 : N < √N < logN