빅 오(Big-O)와 시간복잡도를 어떻게 봐야 하는가

알고리즘이나 자료구조를 공부할 때 가장 먼저 만나게 되는 개념이 시간복잡도다. 하지만 실무에서는 빅 오 표기법을 공식을 외우듯 쓰기보다, 입력 크기가 커질 때 어떤 비용이 병목이 되는지를 판단하는 도구로 이해하는 편이 더 중요하다.

시간복잡도와 공간복잡도

• 시간복잡도: 입력 크기가 증가할 때 실행 시간이 어떻게 늘어나는가
• 공간복잡도: 입력 크기가 증가할 때 필요한 메모리가 어떻게 늘어나는가

둘 다 중요하지만, 일반적인 서버 애플리케이션에서는 시간복잡도가 먼저 병목으로 드러나는 경우가 많다. 다만 캐시, 대량 데이터 처리, 메모리 기반 자료구조를 다룰 때는 공간복잡도도 무시할 수 없다.

왜 빅 오를 쓰는가

실행 시간은 CPU, JVM 상태, 운영체제, 입력 데이터의 분포에 따라 달라진다. 그래서 절대적인 밀리초보다 증가 추세를 보는 표기법이 필요하다.

빅 오 표기법은 상한선 관점에서 성능을 표현한다. 즉, 입력 크기 n이 커질수록 이 알고리즘이 얼마나 빠르게 비싸지는지를 단순화해서 보여준다.

예를 들어:

• O(1): 입력 크기와 무관하게 거의 일정
• O(log n): 입력이 커져도 증가폭이 완만
• O(n): 입력이 두 배가 되면 비용도 대체로 두 배
• O(n log n): 정렬에서 자주 보이는 형태
• O(n^2): 이중 반복문처럼 급격히 커짐

자주 헷갈리는 부분

O(1)은 항상 빠르다는 뜻이 아니다

상수 시간이라고 해서 무조건 빠른 것은 아니다. 상수 항이 매우 크면 작은 입력에서는 O(n)보다 느릴 수도 있다. 빅 오는 증가율을 보여줄 뿐이고, 실제 체감 속도는 구현 세부와 상수 비용도 영향을 준다.

최선, 평균, 최악의 경우를 구분해야 한다

같은 알고리즘도 어떤 입력을 만나느냐에 따라 성능이 달라진다. 실무에서는 평균적인 케이스만 보지 말고, 트래픽이 몰리거나 데이터 편향이 심할 때 최악의 경우가 감당 가능한지도 봐야 한다.

복잡도는 코드 한 줄이 아니라 구조에서 나온다

반복문이 하나라고 해서 무조건 O(n)인 것은 아니고, 반복문이 두 개라고 해서 항상 O(n^2)도 아니다. 중요한 것은 반복의 중첩 관계와 각 단계가 입력 크기에 대해 몇 번 실행되는가다.

시간복잡도 분석 예시

배열 한 번 순회

int sum = 0;
for (int value : arr) {
    sum += value;
}

입력 배열 길이가 n이면 각 원소를 한 번씩 보므로 O(n)이다.

이중 반복문

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // do something
    }
}

바깥 반복이 n, 안쪽 반복이 n이므로 전체는 O(n^2)다.

이진 탐색

while (left <= right) {
    int mid = (left + right) / 2;
    if (target < arr[mid]) {
        right = mid - 1;
    } else if (target > arr[mid]) {
        left = mid + 1;
    } else {
        return mid;
    }
}

탐색 구간을 매번 절반으로 줄이므로 O(log n)이다.

빅 세타와 빅 오메가

복잡도 표기에는 빅 오만 있는 것이 아니다.

• Big-O: 상한선
• Big-Omega: 하한선
• Big-Theta: 상한과 하한이 같은 수준일 때의 타이트한 경계

실무에서는 보통 빅 오만 많이 쓰지만, 알고리즘을 정확히 설명할 때는 이 차이를 알고 있는 것이 좋다.

실무에서 복잡도를 보는 방식

백엔드 개발에서는 알고리즘 문제처럼 복잡도를 계산하는 장면보다, 다음과 같은 상황에서 더 자주 체감한다.

• 리스트를 순회하면서 내부에서 다시 DB나 컬렉션 검색을 하는 경우
• 요청당 전체 데이터를 다시 정렬하거나 그룹핑하는 경우
• 중첩 루프 안에서 외부 API나 캐시 조회를 호출하는 경우
• 대량 배치 처리에서 한 건씩 insert 또는 update를 반복하는 경우

즉, 실무에서의 시간복잡도는 단순한 반복문의 개수보다 요청량, 데이터량, I/O 비용이 중첩되는 구조를 경계하는 감각에 가깝다.

복잡도만 보고 판단하면 안 되는 경우

다음도 함께 봐야 한다.

• 상수 비용이 얼마나 큰가
• 메모리를 얼마나 추가로 쓰는가
• 데이터가 실제로 얼마나 큰가
• 병목이 CPU인지, 메모리인지, 네트워크인지, DB인지

예를 들어 O(n log n) 정렬이 이론상 우수해도, 실제 병목이 정렬이 아니라 DB 조회 수라면 정렬 알고리즘을 바꾸는 것보다 쿼리 수를 줄이는 게 더 큰 효과를 낸다.

정리

빅 오 표기법은 수학 문제를 풀기 위한 장식이 아니라, 코드가 커지는 입력을 만났을 때 어디서 무너질 수 있는지 미리 보는 도구다.

핵심은 다음 세 가지다.

• 증가율을 본다
• 최악의 경우를 의식한다
• 실무에서는 I/O와 결합된 반복 구조를 특히 경계한다

시간복잡도를 정확히 계산하는 습관은 결국 성능 문제를 만났을 때 병목을 더 빨리 좁히는 감각으로 이어진다.