리스트에서 값 하나를 찾는 코드를 짰습니다. 항목이 100개일 때는 눈 깜짝할 사이에 끝났죠. 그런데 서비스가 커져서 100만 개가 되자, 같은 코드가 몇 초씩 멈칫거리기 시작합니다. 코드는 한 글자도 바꾸지 않았는데 왜 갑자기 느려졌을까요?

이 질문에 "데이터가 많아져서요"라고 답하는 건 절반만 맞습니다. 진짜 답은 그 코드가 데이터 양에 대해 어떤 비율로 느려지는가에 있습니다. 그 비율을 계산으로 표현하는 도구가 바로 시간복잡도이고, 그걸 적는 표기법이 빅오(Big-O)입니다.

시간복잡도는 '초'가 아니라 '증가 속도'다

많은 분들이 시간복잡도를 "이 코드가 몇 초 걸리나"로 오해합니다. 하지만 실행 시간은 컴퓨터 성능, 언어, 그날 서버 상태에 따라 다 다릅니다. 같은 코드도 최신 노트북에선 0.1초, 낡은 서버에선 2초가 나옵니다. 그걸로는 코드끼리 비교할 수 없죠.

그래서 우리는 초 대신 연산 횟수가 입력 크기에 따라 어떻게 늘어나는가를 봅니다. 입력 데이터의 개수를 보통 n이라고 부릅니다. n이 2배, 10배, 100배로 커질 때 연산 횟수가 어떤 곡선을 그리는지, 그 '모양'만 떼어내서 표현한 게 빅오입니다.

빅오는 코드의 절대 속도가 아니라, 데이터가 늘어날 때 코드가 버티는 체력을 나타냅니다.

이게 왜 중요하냐면, 개발 초기엔 데이터가 적어서 어떤 코드든 빠릅니다. 문제는 항상 나중에, 데이터가 불어난 뒤에 터집니다. 빅오를 읽을 줄 알면 그 사고를 코드를 짜는 시점에 미리 막을 수 있습니다.

가장 자주 만나는 네 가지 모양

복잡도 종류는 많지만, 실무에서 90%는 아래 네 개 안에서 만납니다. 파이썬 예제로 하나씩 보겠습니다.

O(1) — 상수 시간. 데이터가 아무리 많아도 연산 횟수가 그대로입니다. 대표적으로 딕셔너리(해시맵)에서 키로 값을 꺼내는 경우죠.

users = {"alice": 30, "bob": 25}
age = users["alice"]   # 항목이 100개든 100만 개든 한 번에 찾음

O(n) — 선형 시간. 데이터가 2배 되면 연산도 2배. 리스트를 처음부터 끝까지 훑는 경우입니다.

def find_max(nums):
    biggest = nums[0]
    for x in nums:      # n개를 전부 한 번씩 확인
        if x > biggest:
            biggest = x
    return biggest

O(log n) — 로그 시간. 한 번 확인할 때마다 남은 후보가 절반으로 줄어듭니다. 정렬된 데이터에서의 이진 탐색이 대표적입니다. n이 100만이어도 약 20번이면 끝납니다.

def binary_search(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        elif sorted_nums[mid] < target:
            lo = mid + 1     # 절반을 버림
        else:
            hi = mid - 1     # 나머지 절반을 버림
    return -1

O(n²) — 제곱 시간. 반복문 안에 반복문. 데이터가 10배 되면 연산은 100배가 됩니다. 초보자가 자기도 모르게 가장 많이 만드는 함정입니다.

def has_duplicate(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):   # 이중 반복
            if nums[i] == nums[j]:
                return True
    return False

숫자로 보면 차이가 무섭다

말로는 감이 잘 안 옵니다. n이 커질 때 각 복잡도가 대략 몇 번의 연산을 하는지 표로 보겠습니다.

입력 크기 nO(1)O(log n)O(n)O(n²)
101약 310100
1,0001약 101,0001,000,000
1,000,0001약 201,000,0001조

맨 아랫줄을 보세요. 데이터가 100만 개일 때 O(n)은 100만 번이면 되지만, O(n²)은 1조 번입니다. 초당 1억 번을 처리하는 컴퓨터라도 1조 번이면 약 3시간입니다. 처음 얘기했던 "코드는 그대로인데 갑자기 멈칫대는" 현상의 정체가 바로 이겁니다. 데이터가 적을 땐 O(n)이든 O(n²)이든 둘 다 순식간이라 차이를 못 느꼈던 거죠.

빅오를 읽는 세 가지 실전 규칙

복잡도를 직접 계산할 때 외워두면 편한 규칙이 있습니다.

첫째, 상수는 버립니다. 반복을 3번 돌든 5번 돌든 O(3n), O(5n)이 아니라 그냥 O(n)입니다. n이 무한히 커질 때의 '모양'만 보기 때문에, 앞에 붙은 배수는 의미가 없어집니다.

둘째, 가장 큰 항만 남깁니다. 한 코드에 O(n)짜리 반복과 O(n²)짜리 반복이 같이 있으면, 전체는 더 무거운 O(n²)입니다. n이 커지면 작은 항은 존재감이 사라지니까요.

셋째, 반복문이 겹치는지 세어보세요. 단일 반복이면 대개 O(n), 반복 안에 반복이면 O(n²)입니다. 이 두 가지만 구분해도 성능 사고의 대부분을 예방할 수 있습니다.

그럼 무조건 빠른 복잡도가 정답일까

여기서 중요한 균형 감각이 하나 필요합니다. 모든 코드를 O(1)로 만들 필요는 없습니다. 데이터가 항상 수십 개뿐인 곳이라면, 읽기 쉬운 O(n²) 코드가 억지로 최적화한 복잡한 코드보다 나을 때가 많습니다. 최적화는 '느려서 문제가 생기는 지점'에 집중하는 게 맞습니다.

또 하나, 빅오는 흔히 시간을 말하지만 메모리에도 똑같이 적용됩니다(공간복잡도). 속도를 얻으려고 데이터를 통째로 복사해두면 시간은 빨라져도 메모리가 터질 수 있습니다. 실무의 최적화는 대개 이 둘 사이의 저울질입니다.

정리하면, 시간복잡도는 어려운 이론이 아니라 "이 코드가 데이터가 늘어나도 버틸까?"를 미리 계산하는 습관입니다. 반복문이 겹치는 순간 잠깐 멈춰서 "n이 100만이면?"을 떠올리는 것, 그 작은 습관 하나가 몇 달 뒤의 새벽 장애 호출을 막아줍니다. 오늘 짠 코드에 반복문이 있다면, 한 번 세어보세요. 몇 겹인가요?