실전 Big-O: 수학 불안 없는 복잡도

들어가며 — Big-O가 주는 불안
O()가 실제로 뜻하는 것
자주 나오는 복잡도 클래스
상수가 이길 때 — 작은 n과 캐시
숨어드는 O(n²) — 중첩 루프와 N+1 쿼리
공간 복잡도도 잊지 말자
분할 상환 — 동적 배열의 비밀
언제 최적화를 멈춰야 하나
마치며
참고 자료

들어가며 — Big-O가 주는 불안

Big-O라는 말을 들으면 대학 시절의 극한과 증명이 떠올라 움츠러드는 사람이 많습니다. 하지만 실무에서 Big-O는 시험 문제가 아니라 직관의 도구입니다. "입력이 열 배로 늘면 이 코드는 얼마나 느려질까?"라는 아주 실용적인 질문에 답하기 위한 것입니다.

이 글은 수학적 엄밀함을 잠시 내려놓고, 일하는 엔지니어에게 필요한 만큼의 Big-O를 정리합니다. 극한도 증명도 없이, "이 코드가 큰 입력에서 버틸까?"를 판단하는 감각을 기르는 것이 목표입니다. 정렬 알고리즘이 서로 다른 복잡도로 어떻게 다르게 움직이는지 눈으로 보고 싶다면, 이 사이트의 정렬 시각화 도구를 함께 열어 두면 좋습니다.

O()가 실제로 뜻하는 것

Big-O는 입력 크기가 커질 때, 실행 시간(또는 메모리)이 어떻게 자라는가를 나타냅니다. 핵심 단어는 "자란다(growth)"입니다. 절대적인 속도가 아니라 성장의 모양을 말합니다.

몇 가지 중요한 성질이 있습니다.

상수는 버린다: 2n도 100n도 모두 O(n)입니다. Big-O는 입력이 커질 때의 경향만 보므로, 앞에 붙은 상수 배수는 무시합니다.
낮은 차수는 버린다: n² + n + 5는 O(n²)입니다. n이 아주 커지면 n² 항이 나머지를 압도하므로, 지배적인 항만 남깁니다.
최악의 경우를 기준으로: 보통 Big-O는 최악의 경우(worst case)를 말합니다. "운이 좋으면 빠르다"가 아니라 "아무리 나빠도 이 정도"를 보장하는 관점입니다.

여기서 오해하기 쉬운 지점이 있습니다. Big-O는 "이 코드가 몇 초 걸린다"를 말하지 않습니다. 오직 "입력이 커질 때 어떤 곡선을 그리며 느려진다"만 말합니다. 그래서 두 알고리즘의 실제 속도를 비교하려면 Big-O만으로는 부족할 때가 있는데, 이 점은 뒤에서 다시 다룹니다.

자주 나오는 복잡도 클래스

실무에서 마주치는 복잡도는 사실 몇 개로 압축됩니다. 각각을 현실 예제와 함께 봅시다.

O(1) — 상수 시간. 입력 크기와 무관하게 늘 같은 시간이 걸립니다. 배열의 인덱스 접근, 해시맵(딕셔너리) 조회가 대표적입니다.

# 입력이 아무리 커도 한 번의 접근
value = my_dict[key]      # O(1)
first = my_list[0]        # O(1)

O(log n) — 로그 시간. 매 단계마다 문제의 크기가 절반씩 줄어듭니다. 정렬된 배열에서의 이진 탐색이 전형입니다. 입력이 백만 개여도 약 20단계면 끝납니다.

# 정렬된 배열에서 매번 절반을 버린다 -> O(log n)
import bisect
idx = bisect.bisect_left(sorted_list, target)

O(n) — 선형 시간. 입력을 한 번 훑습니다. 리스트에서 최댓값 찾기, 조건에 맞는 요소 세기처럼 "모든 원소를 한 번씩 보는" 대부분의 작업입니다.

# 모든 원소를 정확히 한 번씩 본다 -> O(n)
total = 0
for x in numbers:
    total += x

O(n log n) — 준선형 시간. 효율적인 정렬 알고리즘(병합 정렬, 퀵 정렬, 팀소트)의 복잡도입니다. 언어 표준 라이브러리의 sort()가 대개 여기에 속합니다. "n개를 정렬한다"는 작업의 사실상 하한선입니다.

O(n²) — 이차 시간. 모든 쌍을 비교하는 작업입니다. 중첩된 두 개의 루프가 각각 입력 전체를 도는 형태에서 나옵니다. 작은 입력에서는 괜찮지만 커지면 급격히 느려집니다.

# 모든 쌍을 비교 -> O(n²)
for i in range(len(items)):
    for j in range(len(items)):
        compare(items[i], items[j])

이 클래스들이 실제로 얼마나 차이 나는지 표로 보면 감이 옵니다.

n	O(log n)	O(n)	O(n log n)	O(n²)
10	약 3	10	약 33	100
1,000	약 10	1,000	약 10,000	1,000,000
1,000,000	약 20	1,000,000	약 2,000만	1조

n이 백만일 때 O(n²)는 1조 번의 연산입니다. 현대 컴퓨터로도 한참 걸립니다. 반면 O(n log n)은 2천만 번으로 순식간이죠. 이 표 하나가 "왜 알고리즘 선택이 중요한가"를 압축해서 보여 줍니다.

상수가 이길 때 — 작은 n과 캐시

여기서 실무의 미묘함이 등장합니다. Big-O는 "n이 충분히 클 때"의 이야기입니다. 그런데 현실의 n은 종종 작습니다. 그리고 작을 때는 버렸던 상수가 다시 중요해집니다.

예를 들어 O(n²)인 삽입 정렬과 O(n log n)인 병합 정렬을 봅시다. 이론상 병합 정렬이 이겨야 하지만, n이 10~20처럼 작으면 삽입 정렬이 더 빠른 경우가 많습니다. 병합 정렬은 재귀 호출, 배열 분할, 병합용 임시 배열 할당 같은 부대 비용(상수)이 크기 때문입니다. 실제로 파이썬과 자바의 표준 정렬은 작은 구간에서는 삽입 정렬로 전환합니다.

캐시도 상수에 큰 영향을 줍니다. 현대 CPU는 연속된 메모리를 읽을 때 훨씬 빠릅니다(캐시 지역성). 그래서 이론상 복잡도가 같거나 살짝 나빠도, 메모리를 연속으로 접근하는 배열이 포인터를 이리저리 따라가는 연결 리스트보다 실제로는 빠른 경우가 흔합니다.

  이론상 복잡도만 보면:
    연결 리스트 중간 삽입 O(1)  vs  배열 중간 삽입 O(n)  -> 리스트 승?

  현실에서는 (캐시 지역성 때문에):
    작은~중간 크기에서 배열이 연결 리스트를 이기는 일이 흔하다
    -> 배열을 순회하며 찾는 비용보다, 포인터 추적의 캐시 미스가 더 비싸다

교훈은 이렇습니다. Big-O는 "큰 그림"을 알려주지만, 실제 성능은 상수와 하드웨어에 달려 있습니다. 두 후보의 Big-O가 같거나 비슷하다면, 답은 이론이 아니라 측정에 있습니다.

숨어드는 O(n²) — 중첩 루프와 N+1 쿼리

O(n²)가 무서운 이유는 종종 눈에 잘 안 띄기 때문입니다. 명시적인 이중 for 루프는 알아채기 쉽지만, 함정은 대개 숨어 있습니다.

첫 번째 함정은 루프 안에 숨은 선형 연산입니다.

# 겉보기엔 루프가 하나뿐이라 O(n) 같지만...
result = []
for item in items:           # n번 반복
    if item in result:       # 리스트 in 검사는 O(n)!
        continue
    result.append(item)
# 실제로는 O(n²) - 매 반복마다 result 전체를 훑는다

item in result에서 result는 리스트이므로, in 검사가 매번 O(n)입니다. 이것이 O(n) 루프 안에 들어가 전체가 O(n²)가 됩니다. 해결책은 in 검사를 O(1)로 만드는 것, 즉 집합(set)을 쓰는 것입니다.

# 집합의 in 검사는 O(1) -> 전체가 O(n)
seen = set()
result = []
for item in items:
    if item in seen:
        continue
    seen.add(item)
    result.append(item)

두 번째 함정은 백엔드 개발에서 악명 높은 N+1 쿼리 문제입니다.

# 게시글 100개를 가져온 뒤(쿼리 1번)...
posts = db.query("SELECT * FROM posts LIMIT 100")
for post in posts:
    # 각 게시글의 작성자를 개별 쿼리로 가져온다 -> 100번의 쿼리!
    author = db.query("SELECT * FROM users WHERE id = ?", post.author_id)
    print(author.name)
# 총 1 + 100 = 101번의 쿼리

게시글이 늘수록 쿼리 수가 선형으로 늘어, 데이터가 커지면 응답이 급격히 느려집니다. 각 쿼리에는 네트워크 왕복 비용이 붙기 때문에 체감은 더 나쁩니다. 해결책은 한 번의 쿼리로 필요한 데이터를 함께 가져오는 것입니다(조인이나 IN 절, ORM의 eager loading).

# 필요한 작성자를 한 번에 가져온다 -> 쿼리 2번
posts = db.query("SELECT * FROM posts LIMIT 100")
author_ids = [p.author_id for p in posts]
authors = db.query("SELECT * FROM users WHERE id IN (...)", author_ids)
# 쿼리 총 2번으로 해결

N+1은 코드만 보면 평범한 루프라 알아채기 어렵습니다. ORM이 뒤에서 쿼리를 대신 날려 주기 때문에 더욱 숨습니다. 쿼리 로그를 켜 두고 "이 페이지 한 번 여는 데 쿼리가 몇 번 나가는가"를 확인하는 습관이 이 함정을 막아 줍니다.

공간 복잡도도 잊지 말자

Big-O는 시간에만 쓰이는 것이 아닙니다. 공간 복잡도는 알고리즘이 추가로 얼마나 많은 메모리를 쓰는지를 같은 방식으로 나타냅니다.

# 시간 O(n), 공간 O(1) - 추가 메모리는 변수 몇 개뿐
def sum_list(numbers):
    total = 0
    for x in numbers:
        total += x
    return total

# 시간 O(n), 공간 O(n) - 입력 크기에 비례하는 새 리스트를 만든다
def double_all(numbers):
    return [x * 2 for x in numbers]

시간과 공간은 종종 맞바꿈(trade-off) 관계입니다. 앞서 중복 제거에서 집합을 쓴 것이 좋은 예입니다. seen 집합에 O(n)의 추가 메모리를 쓴 대가로, 시간 복잡도를 O(n²)에서 O(n)으로 낮췄습니다. 메모리를 조금 더 써서 시간을 크게 아낀 것이죠.

실무에서 공간 복잡도는 특히 대용량 데이터에서 중요합니다. 파일이 메모리보다 크면 "전부 리스트로 읽어 들이는" O(n) 공간 방식은 아예 죽어 버립니다. 이럴 때는 한 줄씩 흘려 처리하는 스트리밍(공간 O(1))으로 바꿔야 합니다. 시간이 빨라도 메모리가 터지면 프로그램은 돌지 않습니다.

분할 상환 — 동적 배열의 비밀

한 가지 미묘하지만 중요한 개념이 분할 상환(amortized) 복잡도입니다. "가끔 비싼 연산이 있지만, 여러 번에 걸쳐 평균 내면 싸다"는 관점입니다.

파이썬의 리스트나 다른 언어의 동적 배열에 원소를 추가하는 append가 대표적입니다. 대개 O(1)이지만, 배열이 꽉 차면 더 큰 배열을 새로 할당하고 기존 원소를 전부 복사해야 합니다. 이 복사는 O(n)입니다.

  용량 4짜리 배열에 계속 append:
  [a][b][c][d]  <- 꽉 참
  다음 append -> 용량 8로 확장, 4개 복사 (이번 한 번은 O(n))
  [a][b][c][d][e][_][_][_]
  이후 5번의 append는 다시 각각 O(1)

그런데 배열을 확장할 때 보통 크기를 두 배로 늘립니다. 그 덕분에 비싼 복사가 점점 드물게 일어납니다. n개를 추가하는 전체 비용을 다 더해서 n으로 나누면, 한 번의 append당 평균 비용은 O(1)로 수렴합니다. 이것이 분할 상환 O(1)입니다.

핵심은 개별 최악의 경우(O(n))만 보고 겁먹지 말라는 것입니다. 그 비싼 연산이 얼마나 드물게 일어나는지를 함께 봐야 실제 성능을 제대로 이해할 수 있습니다. 해시맵의 삽입도 같은 원리로 분할 상환 O(1)입니다.

언제 최적화를 멈춰야 하나

마지막으로, 아마 가장 중요한 실무 감각입니다. Big-O를 배우면 모든 코드를 최적화하고 싶어지지만, 대부분의 코드는 최적화할 필요가 없습니다.

도널드 크누스의 유명한 말이 있습니다. "섣부른 최적화는 만악의 근원이다(premature optimization is the root of all evil)." 아직 병목인지도 모르는 코드를 미리 복잡하게 최적화하면, 가독성만 해치고 이득은 없습니다.

판단 기준을 정리하면 이렇습니다.

n이 작고, 앞으로도 작다면: O(n²)여도 괜찮습니다. 100개짜리 리스트를 이중 루프로 도는 것은 눈 깜짝할 사이입니다. 명확한 코드가 최적화된 코드보다 낫습니다.
핫 패스인가: 이 코드가 초당 수천 번 호출되는 경로인가, 아니면 하루에 한 번 도는 배치인가? 자주 실행되는 곳부터 최적화합니다.
먼저 측정하라: 추측하지 말고 프로파일러로 실제 병목을 찾으세요. 개발자의 직관은 병목 위치를 자주 틀립니다. 시간의 90%를 잡아먹는 10%를 찾아, 거기만 손보는 것이 효율적입니다.
알고리즘부터, 그다음 상수: 최적화가 필요하다면 O(n²)를 O(n)으로 바꾸는 알고리즘 개선이, 상수를 깎는 미세 튜닝보다 훨씬 큰 효과를 냅니다.

즉, Big-O는 "언제나 최적화하라"는 명령이 아니라, "커질 위험이 있는 곳을 미리 알아보는" 레이더입니다. 작은 데이터에는 명확한 코드를, 커질 데이터에는 좋은 복잡도를 선택하는 균형 감각이 실무의 핵심입니다.

마치며

Big-O는 수학 시험이 아니라 엔지니어의 직관 도구입니다. "입력이 커지면 이 코드가 어떻게 될까?"라는 질문에 답하기 위한 것이지요. O(1), O(log n), O(n), O(n log n), O(n²) 같은 몇 개의 클래스만 몸에 익히면 대부분의 상황을 판단할 수 있습니다.

동시에 잊지 말아야 할 것은, Big-O가 전부는 아니라는 점입니다. 작은 n에서는 상수와 캐시가 이기고, 진짜 병목은 프로파일러로 찾아야 하며, 대부분의 코드는 명확함이 최적화보다 중요합니다. 복잡도를 아는 것은 언제 최적화할지를 아는 것이고, 더 중요하게는 언제 최적화하지 않아도 되는지를 아는 것입니다.

정렬 알고리즘들이 같은 데이터를 놓고 얼마나 다르게 움직이는지 눈으로 보고 싶다면, 정렬 시각화 도구에서 O(n²)와 O(n log n)의 차이를 직접 느껴 보세요. 표의 숫자보다 훨씬 생생하게 다가올 겁니다.

참고 자료

Cormen 외, "Introduction to Algorithms" (성장률과 점근 표기)
Donald Knuth, "Structured Programming with go to Statements" (섣부른 최적화 인용의 출처)
Big-O Cheat Sheet: https://www.bigocheatsheet.com/
"What is N+1 query problem": https://www.geeksforgeeks.org/what-is-the-n1-query-problem/