시간복잡도와 빅오 표기법 (Time Complexity, Big-O Notation)

한 줄 정의: 입력 데이터의 크기가 커질 때 알고리즘의 실행 시간이 얼마나 빠르게 늘어나는지를 O(n)과 같은 표기법으로 나타낸 것입니다.

쉽게 풀면

두꺼운 종이 전화번호부에서 특정 이름을 찾는다고 해봅시다. 첫 장부터 한 장씩 넘기며 찾으면, 이름 수가 두 배로 늘어날 때 걸리는 시간도 대략 두 배로 늘어납니다(선형, O(n)). 반면 가나다순으로 정렬된 것을 이용해 항상 중간을 펴서 찾는 범위를 절반씩 좁혀가면, 이름 수가 두 배로 늘어도 걸리는 시간은 아주 조금만 늘어납니다(로그, O(log n)). 이렇게 "입력이 커질 때 처리 시간이 어떤 속도로 늘어나는가"를 대략적인 형태로 나타낸 것이 시간복잡도이고, 이를 O(n), O(log n), O(n²)처럼 표기하는 방식이 빅오 표기법입니다.

왜 중요한가

시간복잡도는 특정 하드웨어나 구현 방식에 의존하지 않고 알고리즘 자체의 효율성을 비교할 수 있는 공통 언어이기 때문에, 새로운 알고리즘이나 자료구조를 제안하는 거의 모든 논문에서 성능을 뒷받침하는 핵심 근거로 등장합니다. 대용량 데이터를 다루는 분야일수록 입력 크기가 커질 때의 증가 속도가 실제 실행 가능성을 좌우하므로, 데이터베이스·머신러닝·그래프 알고리즘 등 다양한 세부분야에서 방법론의 우수성을 주장하는 데 활용됩니다.

논문에서는 이렇게 쓰입니다

"제안한 알고리즘의 시간복잡도는 O(n log n)으로, 기존 O(n²) 방식보다 대용량 데이터 처리에 효율적임을 실험적으로 확인하였다."

이 문장은 새로 제안한 방법이 데이터 양이 늘어날수록 기존 방법보다 훨씬 적은 시간 증가율로 처리할 수 있음을 이론적인 표기법으로 보여준다는 뜻입니다. 알고리즘·컴퓨터공학 논문에서는 성능을 실행 시간(초)뿐 아니라 이런 표기법으로도 함께 제시하는 경우가 많습니다.

"제안된 그래프 순회 기법은 O(V+E)의 시간복잡도를 가지며, 정점과 간선 수에 대해 선형적으로 확장 가능함을 보였다."

정점(V)과 간선(E) 수를 합한 만큼만 시간이 늘어나는 방식이어서, 그래프가 커져도 처리 시간이 급격히 늘지 않고 완만하게 늘어난다는 뜻입니다.

"제안한 신경망 구조는 어텐션 연산의 시간복잡도를 O(n²)에서 O(n log n)으로 낮춰 긴 시퀀스 처리에서의 계산 비용을 줄였다."

입력 문장이 길어질 때 계산량이 급격히 늘어나던 기존 방식을 개선해, 길이가 늘어나도 계산량이 상대적으로 덜 늘어나도록 만들었다는 뜻입니다.

조금 더 깊게 보면

논문에서는 최악의 경우를 나타내는 빅오(O) 외에도, 최선의 경우를 나타내는 빅오메가(Ω)나 평균적인 경우를 다루는 빅세타(Θ) 표기법이 함께 언급되기도 합니다. 또한 시간복잡도와 별개로 알고리즘이 사용하는 메모리 양을 나타내는 공간복잡도(space complexity)도 자주 함께 제시되며, 실제 성능 비교에서는 이론적 복잡도 외에 상수항이나 캐시 효율, 병렬화 가능성 같은 요소도 실행 시간에 영향을 준다는 점을 고려하는 경우가 많습니다.

주의할 점

빅오 표기법은 보통 "최악의 경우(worst case)"를 기준으로 나타내며, 실제 초 단위 실행 시간이 아니라 데이터가 늘어날 때의 "증가 속도"를 비교하는 개념입니다. 같은 O(n log n)이라도 정렬 알고리즘의 종류나 하드웨어에 따라 실제 걸리는 시간은 다를 수 있습니다.