알고리즘의 효율성을 나타내는 빅오 표기법
빅오(Big O) 표기법은 점근적 표기법(Asymptotic Notation)의 하나로 Landau symbol이라고 부르기도 하며, 알고리즘의 효율성(시간 복잡도)를 나타낼 때 사용합니다.
그렇다면 점근적 표기법이란 무엇일까?
점근적 표기법은 중요하지 않은 상수와 계수를 제거하여 알고리즘의 복잡도를 단순화하여 나타낼 때 사용하는 표기법입니다.
점근적 표기법은 빅 세타(Big-θ), 빅 오(Big-O), 빅 오메가(Big-Ω)가 있으며 대략적인 의미는 다음과 같습니다.
| 빅 오(Big-O) | 점근적 상한에 대한 표기 | ex) O(n²) |
| 빅 세타(Big-θ) | 상한과 하한의 평균에 대한 표기 | ex) θ(n²) |
| 빅 오메가(Big-Ω) | 점근적 하한에 대한 표기 | ex) Ω(n²) |
빅 세타와 빅 오메가는 원하는 효율성을 정확하게 나타내지 못하는 관계로 빅 오 표기법이 주로 사용됩니다.
알고리즘의 대략적인 실행 시간만 알면 되므로 빅 오 표기법은 차수가 가장 높은 항만 사용해 수행 시간의 상한(최악의 경우)을 나타냅니다.
예를 들어 f(n)=3n²+2n+1일 때, 빅 오 표기법을 사용하면 O(n²)로 나타낼 수 있습니다.
입력값이 작을 때는 문제가 없지만 입력값이 무한대에 가까워지는 경우에는 기하 급수적으로 복잡도가 증가하며 주요 증가율은 다음과 같습니다.
| 시간 복잡도 | n이 2배가 될 경우 |
| O(1) | 변함 X |
| O(log n) | 약간 증가 |
| O(n) | 2배 증가 |
| O(n log n) | 2배보다 약간 증가 |
| O(n2) | 4배 증가 |
| O(n3) | 8배 증가 |
| O(nk) | 2k배 증가 |
| O(kn) | kn배 증가 |
| O(n!) | nn배 증가 |
증가율을 그래프로 보면 다음과 같습니다.
그래프 기울기가 완만할수록 효율이 좋은 것을 나타내며 기울기가 가파를수록 효율성이 나쁜 것을 의미합니다.
위 그래프를 통해 상수->로그->선형->다항->지수->팩토리얼의 순으로 효율이 떨어지고 있는 것을 알 수 있습니다.