Big-O(빅오) 표기법
in DEV on Backend 빅오표기법 Big-o 시간복잡도 Time-complexity 알고리즘 Algorithm 백엔드 컴퓨터사이언스 Cs 성능최적화 쿼리최적화
개발을 하다보면 ‘이 코드의 시간 복잡도는 \(O(N)\) 이다.’, ‘이 쿼리는 \(O(N^2)\)이라 위험하다.’와 같은 말을 자주 듣는다.
여기서는 서비스의 성능과 직결되는 Big-O(빅오) 표기법에 대해 가볍게 훑어본다.
Big-O(빅오) 표기법이란?
‘입력 데이터의 크기(N)가 늘어날 때, 프로그램의 실행 시간이 얼마나 늘어나는가?’
Big-O 표기법은 알고리즘의 효율성을 수학적으로 나타낸 표기법이다.
- 컴퓨터 성능과 무관
- 하드웨어가 아무리 좋아도 알고리즘 자체가 비효율적이면 데이터가 커졌을 때 터지게 된다.
- Big-O는 하드웨어 사양을 배제하고 알고리즘 자체의 구조적 성능만 평가한다.
- 최악의 시나리오 기준
- ‘아무리 안 좋아도 이 정도 시간 안에는 끝난다.’는 성능의 상한선을 보장하기 위해 주로 최악의 경우를 기재한다.
주요 시간 복잡도 한 눈에 보기
\[\text{(빠름) } O(1) < O(\log N) < O(N) < O(N \log N) < O(N^2) < O(2^N) \text{ (느림)}\]시간 복잡도(Big-O) 표기법
| 표기법 | 명칭 | 설명 | 대표적인 예시 |
|---|---|---|---|
| \(O(1)\) | 상수 시간 (Constant) | 데이터 양과 상관없이 항상 일정한 시간 소요 | 배열 인덱스 접근, 해시맵(HashMap) 조회 |
| \(O(\log N)\) | 로그 시간 (Logarithmic) | 데이터가 늘어나도 수행 시간이 매우 천천히 증가 | 이진 탐색(Binary Search), DB B-Tree 인덱스 |
| \(O(N)\) | 선형 시간 (Linear) | 데이터 양에 정비례하여 시간 증가 | 단일 반복문(for), DB Full Table Scan |
| \(O(N \log N)\) | 선형 로그 시간 | \(O(N)\)보다는 느리지만 효율적인 정렬 알고리즘 | 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) 평균 |
| \(O(N^2)\) | 2차 제곱 시간 (Quadratic) | 데이터가 늘어나면 작업량이 제곱으로 폭발 | 중첩 반복문 (2중 for문), 상관 서브쿼리 |
| \(O(2^N)\) | 지수 시간 (Exponential) | 데이터가 1개 늘어날 때마다 작업량이 2배씩 곱해짐 | 단순 재귀 피보나치 수열 |
Big-O 계산 규칙
① 상수는 버린다.
N이 무한히 커지면 비례 계수인 상수는 의미가 사라진다.
\(O(2N) \rightarrow \mathbf{O(N)}\)
\(O(50) \rightarrow \mathbf{O(1)}\)
② 가장 영향력이 큰 항만 남긴다.
최악의 상황에서 최고차항이 압도적인 비중을 차지하므로 낮은 차수의 항은 무시한다.
\(O(N^2 + N + 100) \rightarrow \mathbf{O(N^2)}\)
실무 개발자를 위한 요약
- \(O(1)\) ~ \(O(N \log N)\)
- 실무/운영 환경에서 권장하는 안정적인 성능 범위
- \(O(N^2)\) 이상
- 데이터가 적을때는 티가 안 나지만, 수십만 건 이상의 실제 DB나 서버 환경에 올라가는 순간 서비스 지연 및 서버 다운을 유발하는 주범
- 인덱스 안 탄 쿼리, 중첩 반복문 등
