빅오 표기법(Big O notation)을 알아보자

알고리즘의 효율성을 나타내는 빅오 표기법

빅오(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배 증가

증가율을 그래프로 보면 다음과 같습니다.

그래프 기울기가 완만할수록 효율이 좋은 것을 나타내며 기울기가 가파를수록 효율성이 나쁜 것을 의미합니다.

출처 : https://en.wikipedia.org/wiki/Big_O_notation

위 그래프를 통해 상수->로그->선형->다항->지수->팩토리얼의 순으로 효율이 떨어지고 있는 것을 알 수 있습니다.