빅오 표기법(Big-O)
빅오 표기법 : 알고리즘의 효율성을 표기해주는 표기법
특징
-
수항을 무시한다
- O(2n)의 경우 상수를 무시하여 O(n)으로 표기
-
가장크게 영향력을 주는 부분을 제외하고 나머지는 표기를 안한다. (함수의 상한만 나타냄)
- O(2^n + n^2) -> O(2^n)으로 표기
시간 복잡도
알고리즘을 위해 필요한 연산 횟수. 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리지는지를 의미
특징 : 시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용
| 빅오 표기법 | 제목2 |
|---|---|
| O(1) | 상수 시간 |
| O(logN) | 로그 시간 |
| O(N) | 선형 시간 |
| O(NlogN) | 로그 선형 시간 |
| O(N²) | 이차 시간 |
| O(2ᴺ) | 지수 시간 |
remind