빅오 표기법 (big-O notation)
쉽게 풀면
빅오 표기법은 알고리즘이 얼마나 빠른지를 입력의 크기가 아주 커졌을 때의 경향으로 요약해서 표현하는 방법이다. 예를 들어 O(n)은 입력이 두 배가 되면 실행 시간도 대략 두 배가 된다는 뜻이고, O(n^2)은 입력이 두 배가 되면 실행 시간은 대략 네 배가 된다는 뜻이다. 이 표기법은 세부적인 상수(예: 정확히 몇 밀리초 걸리는지)는 무시하고 '입력이 커질수록 얼마나 가파르게 느려지는가'라는 큰 그림에 집중하기 때문에, 서로 다른 알고리즘의 근본적인 효율성을 하드웨어나 구현 세부사항과 무관하게 비교할 수 있게 해준다.
왜 중요한가
빅오 표기법은 새로운 알고리즘이나 자료구조를 제안하는 논문에서 그 기여를 객관적으로 뒷받침하는 핵심 근거로 쓰인다. 실행 환경이나 하드웨어에 따라 달라지는 실제 실행 시간 대신, 입력 크기에 따른 이론적 확장성을 공통 언어로 제시할 수 있기 때문에 서로 다른 연구에서 제안한 방법들을 공정하게 비교할 수 있게 해준다. 특히 대규모 데이터나 대규모 모델을 다루는 분야에서는 계산 복잡도가 실제로 방법을 적용할 수 있는지 여부를 좌우하므로, 시간·공간 복잡도 분석은 이론 논문뿐 아니라 시스템·응용 논문에서도 널리 요구된다.
논문에서는 이렇게 쓰입니다
알고리즘의 효율성을 입력 크기에 따른 점근적 증가율로 정량화해 비교할 때 표준적으로 사용된다.
데이터베이스나 정보 검색 분야에서는 질의 처리 성능을 표현할 때 이러한 방식으로 빅오 표기법을 활용해 자료구조 선택의 근거를 제시한다.
딥러닝, 특히 자연어처리 분야에서는 모델 구조가 입력 길이에 따라 얼마나 확장 가능한지를 설명할 때 빅오 표기법을 사용하며, 이는 모델의 실용적 한계를 논의하는 근거로 이어진다.
조금 더 깊게 보면
실제 논문을 읽다 보면 빅오(O, 상한)와 함께 빅오메가(Ω, 하한), 빅세타(Θ, 상한과 하한이 같은 경우의 타이트한 경계) 표기법이 함께 언급되기도 하는데, 이들은 점근적 성능을 얼마나 정밀하게 특정하느냐에서 차이가 있다. 또한 논문에서 제시하는 복잡도는 대체로 최악의 경우(worst-case)를 기준으로 하지만, 실제 응용에서는 평균적인 경우(average-case)나 여러 번의 연산에 걸쳐 비용을 나누어 계산하는 상각 분석(amortized analysis)이 더 현실적인 지표로 쓰이기도 한다. 시간 복잡도뿐 아니라 공간(메모리) 복잡도도 같은 표기법으로 표현되며, 두 지표 사이의 트레이드오프를 함께 논의하는 경우도 흔하다.
주의할 점
빅오 표기법은 입력이 충분히 커졌을 때의 점근적 경향을 나타낼 뿐이므로, 입력 크기가 작은 경우에는 이론적으로 더 느린 알고리즘이 상수 계수 덕분에 실제로는 더 빠를 수도 있다는 점에 유의해야 한다.