시간 복잡도: 자료가 늘면 얼마나 느려지나(빅오)

코드가 칸 10개에서는 빨랐는데 100만 개에서는 멈춘 듯합니다. 왜 그런지는 「자료가 두 배가 되면 걸음이 몇 배가 되나」로 설명됩니다. n 을 움직이며 여섯 가지 모양을 비교하고, 값 찾기의 걸음을 직접 세어 보세요.

한 줄 답. 시간 복잡도(time complexity)는 자료의 수 n 이 늘 때 연산 횟수가 어떤 모양으로 늘어나나입니다. 초가 아닙니다. 빅오 표기(Big O notation, O(…))로 적고, 상수와 작은 항은 버립니다. O(n) 은 n 이 두 배면 두 배, O(n²) 은 네 배, O(log n) 은 한 걸음만 더입니다. 그래서 n 이 커지면 모양의 차이가 기계의 빠르기 차이를 이깁니다.

모양n 이 두 배가 되면이런 일지금 n 의 연산 횟수
O(1)그대로리스트의 k 번째 칸 읽기
O(log n)한 걸음 더정렬된 칸에서 반씩 잘라 찾기(이진 탐색, binary search)
O(n)두 배앞에서부터 하나씩 찾기(선형 탐색, linear search)
O(n log n)두 배보다 조금 더정렬
O(n²)네 배모든 둘씩 짝을 비교하기(for 안에 for)
O(2ⁿ)n 이 하나만 늘어도 두 배모든 부분집합 훑기

그림 읽기: 가로는 1 부터 2n 까지입니다. 세로 점선이 지금 n 이고, 그 왼쪽 숫자가 지금 n 의 연산 횟수입니다. 굽은 화살표는 n 이 2n 으로 두 배가 될 때이고, 화살표 위의 ×2·×4 는 몇 배, +1 은 몇 더입니다. 곡선 이름은 색과 함께 오른쪽 끝에, 위로 나간 곡선은 나간 자리에 「↑」로 적습니다.

막대나 숫자 칸으로 n 을 바꿔 보세요(2 ~ 1000). 연산 횟수는 식에 n 을 넣은 값이고, 0.1 에서 반올림했습니다(log₂n 은 n 이 2 의 거듭제곱이 아니면 정수가 아닙니다). 2ⁿ 은 n = 53 부터 「셀 수 없이 큼」으로 적습니다. 그보다 크면 이 쪽의 숫자로는 정수를 정확히 적을 수 없습니다.

해 볼 것. ① 처음 n = 8 에서 연산 횟수는 1, 3, 8, 24, 64, 256 입니다. 그림은 2n = 16 까지 그립니다. 점선(n = 8)에서 2ⁿ 은 벌써 위로 나갔고, n² 은 64 로 아직 안에 있다가 16 에 닿기 전에 위로 나갑니다. 화살표 이름표는 1 이 ×1, log₂n 이 +1, n 이 ×2, n·log₂n 이 ×2.7 이고, 위로 나간 n² 은 ×4, 2ⁿ 은 ×256 입니다. ② n 을 16 으로 두 배 하면 4, 16, 64, 256, 65,536 입니다. log₂n 은 하나 늘고(3 → 4), n 은 두 배, n² 은 네 배(64 → 256), 2ⁿ 은 제곱(256 → 65,536)이 됩니다. ③ n = 52 에서 2ⁿ 은 4,503,599,627,370,496 이고, 53 부터 셀 수 없이 큽니다. ④ n = 1000 이면 log₂n 은 10, n 은 1,000, n·log₂n 은 9,965.8, n² 은 1,000,000 입니다. 그림에서 1 과 log₂n 은 바닥에 붙고, n 도 바닥 가까이 내려갑니다.

1. 빅오가 재는 것: 초가 아니라 늘어나는 모양

실행 시간은 대략 한 걸음에 드는 시간 × 연산 횟수 입니다. 앞의 것은 기계, 언어, 캐시가 정합니다. 뒤의 것은 알고리즘과 자료의 수 n 이 정합니다. 시간 복잡도는 뒤의 것만 봅니다. 걸음은 칸 하나 읽기, 값 둘 비교하기처럼 한 번에 끝나는 일 하나입니다.

그래서 빅오는 초를 말하지 않습니다. 「n 이 두 배가 되면 걸음이 몇 배가 되나」를 말합니다. 열 배 빠른 컴퓨터로 바꿔도 O(n²) 인 코드는 n 이 두 배면 여전히 네 배 걸립니다. n 이 충분히 커지면 모양이 나쁜 쪽은 빠른 기계로도 따라잡지 못합니다. 위 실험의 n = 1000 에서 n² 은 n 의 1,000 배입니다.

책의 정의는 이렇습니다. n 이 충분히 클 때 f(n) 이 g(n) 의 어떤 상수 배를 넘지 않으면 f(n) = O(g(n)) 이라고 씁니다. 곧 빅오는 「이보다 빨리 늘지는 않는다」는 상한(upper bound)입니다. 보통은 그 가운데 가장 딱 맞는 모양을 적습니다.

2. 걸음을 실제로 세어 보기: 값 찾기 두 방법

작은 것부터 정렬된 칸 n 개(2, 4, 6, …, 2n)에서 값 하나를 찾습니다. 선형 탐색은 첫 칸부터 차례로 봅니다. 이진 탐색은 남은 범위의 가운데 칸을 보고, 찾는 값보다 작으면 왼쪽 절반을, 크면 오른쪽 절반을 버립니다. 정렬돼 있으니 버린 쪽에는 찾는 값이 있을 수 없습니다. 아래 실험은 두 방법을 실제로 돌리며 칸을 볼 때마다 한 걸음으로 셉니다.

칸이 넓으면 칸 안에 값을, 아래 띠 밑에 본 차례(1, 2, 3, …)를 적습니다. 칸이 좁아지면 본 칸만 칠합니다. 「없는 값」은 맨 뒤 값보다 1 큰 홀수입니다.

해 볼 것. ① 처음(8칸, 맨 뒤 값 16)은 선형 탐색 8 걸음, 이진 탐색 4 걸음입니다. 이진 탐색이 본 값은 8, 12, 14, 16 입니다(3절의 표). ② 「맨 앞 값」은 선형 탐색 1 걸음, 이진 탐색 3 걸음이고, 「가운데 값」(8)은 선형 탐색 4 걸음, 이진 탐색 1 걸음입니다. 최선의 경우는 방법마다 다릅니다. ③ n 을 500 으로 두고 맨 뒤 값을 찾으면 500 걸음과 9 걸음, 1000 으로 두 배 하면 1,000 걸음과 10 걸음입니다. 선형 탐색은 두 배, 이진 탐색은 한 걸음 더입니다. ④ 「없는 값」은 두 방법 모두 맨 뒤 값과 같은 걸음이 듭니다. 끝까지 봐야 없다는 것을 압니다.

3. 손으로 따라가기: 8칸에서 16 찾기

실험 ② 의 처음과 같은 입력입니다. 칸은 2, 4, 6, 8, 10, 12, 14, 16 이고 칸 번호는 0 부터 7 까지입니다. 찾는 값은 16 입니다.

선형 탐색. 2, 4, 6, 8, 10, 12, 14 를 보고 아니어서 넘어가고, 여덟째에 16 을 만납니다. 8 걸음입니다. 맨 뒤에 있으니 칸 수만큼 듭니다.

이진 탐색. 가운데 칸 번호는 (왼쪽 끝 + 오른쪽 끝) ÷ 2 를 내림한 것입니다.

걸음남은 범위(칸 번호)가운데 칸그 값16 과 비교하면다음
10 ~ 7 (8칸)38작다(8 < 16). 정렬돼 있으니 16 은 오른쪽에만 있을 수 있다0 ~ 3 을 버린다 → 4 ~ 7
24 ~ 7 (4칸)512작다(12 < 16). 16 은 오른쪽에만 있을 수 있다4 ~ 5 를 버린다 → 6 ~ 7
36 ~ 7 (2칸)614작다(14 < 16). 16 은 오른쪽에만 있을 수 있다6 을 버린다 → 7 ~ 7
47 ~ 7 (1칸)716같다(16 = 16)찾았다
걸음 1 2 4 6 8 10 12 14 16 ▼ 8칸 8 < 16 ÷2 걸음 2 2 4 6 8 10 12 14 16 ▼ 4칸 12 < 16 ÷2 걸음 3 2 4 6 8 10 12 14 16 ▼ 2칸 14 < 16 ÷2 걸음 4 2 4 6 8 10 12 14 16 ▼ 1칸 16 = 16 찾음
남은 칸이 8 → 4 → 2 → 1 로 반씩 줍니다. 걸음마다 남은 범위(아래 괄호)의 가운데 칸(파랑, ▼)을 보고 16 과 비교합니다. 16 이 더 크면 가운데까지 왼쪽을 버립니다(흐린 칸). 넷째 걸음에 주황 테두리 칸에서 찾습니다.

남은 칸이 8 → 4 → 2 → 1 로 반씩 줄었습니다. 8 을 1 이 될 때까지 반으로 자르는 횟수가 log₂8 = 3 이고, 마지막 한 칸을 보는 한 걸음을 더해 4 걸음입니다. 일반으로는 많아야 ⌊log₂n⌋ + 1 걸음입니다(⌊ ⌋ 는 내림). n = 1000 이면 10 걸음입니다. 칸이 두 배가 되면 반으로 자를 일이 한 번 늘 뿐이라서 O(log n) 입니다. 이 방법은 이진 탐색 쪽에서 더 자세히 봅니다.

4. 규칙: 상수와 작은 항을 버린다

규칙예까닭
상수 배는 버린다3n → O(n)상수는 기계와 언어가 바꾸는 몫입니다. n 이 두 배일 때 몇 배가 되나는 상수와 상관없습니다
작은 항은 버린다n² + 100n → O(n²)n = 1,000 이면 n² 은 1,000,000, 100n 은 100,000 입니다. n = 100,000 이면 10,000,000,000 대 10,000,000 으로, 작은 항이 0.1% 입니다. n 이 클수록 큰 항만 남습니다
차례로 하면 큰 쪽만 남는다정렬(n log n) 뒤 한 번 훑기(n) → O(n log n)둘을 더하면 작은 쪽이 작은 항이 됩니다
안에 넣으면 곱한다n 번 도는 for 안에 n 번 도는 for → O(n²)바깥 한 바퀴마다 안쪽이 n 걸음입니다
로그의 밑은 적지 않는다log₂n 과 log₁₀n 은 둘 다 O(log n)밑을 바꾸면 상수 배만 달라집니다(log₂n ≈ 3.32 × log₁₀n)
n = 4 4 × 4 = 16칸 n 두 배 칸 ×4 안쪽 for: 한 줄 8 걸음 바깥 for: 8 줄 n = 8 8 × 8 = 64칸
n 이 두 배면 칸은 네 배(16 → 64). 「안에 넣으면 곱한다」를 칸으로 그렸습니다. 가로 한 줄이 안쪽 for 의 n 걸음이고, 줄의 수가 바깥 for 의 n 바퀴입니다. 둘 다 두 배가 되니 2 × 2 = 4 배입니다. 실험 ① 에서 n = 8 일 때 n² 이 64 인 것과 같은 칸 수입니다.

버리는 까닭은 하나입니다. 빅오는 n 이 커질 때 무엇이 이기는지 보려는 도구라서, n 이 커지면 어차피 묻히는 것을 들고 다니지 않습니다. 대신 n 이 작을 때는 버린 것이 크게 남을 수 있습니다(자주 묻는 것 1). Princeton 의 알고리즘 교재는 작은 항만 버리고 앞의 상수는 남기는 물결표 표기를 씁니다: 3n² + 100n ~ 3n². 빅오는 거기서 상수 3 까지 버린 것입니다.

5. 최악의 경우와 평균의 경우

같은 n 이라도 입력에 따라 연산 횟수가 다릅니다. 실험 ② 에서 본 것처럼 찾는 값이 어디 있느냐에 따라 1 걸음일 수도, n 걸음일 수도 있습니다. 그래서 어느 경우를 말하는지 같이 적습니다.

6. 메모리도 같은 방식으로 잰다

메모리는 입력 말고 더 드는 칸이 n 에 따라 어떻게 늘어나나로 잽니다(공간 복잡도, space complexity). 규칙은 시간과 같습니다.

시간과 메모리는 서로 바꿀 수 있습니다. 리스트에서 값을 여러 번 찾을 일이 있으면 set 이나 dict 를 한 번 만들어 둡니다. 메모리가 n 칸 더 들지만 찾기가 O(n) 에서 보통 O(1) 로 줍니다. Princeton 교재는 메모리를 바이트로 셀 때 변수의 수에 그 종류가 쓰는 바이트를 곱해 더합니다(Java 기준).

7. 흔한 일의 연산 횟수: 언제 무엇을 쓰나

Python 문서(CPython 기준)에 적힌 값입니다. 쉬운 말은 실험 ① 의 표와 같습니다: O(1) 은 n 과 상관없음, O(log n) 은 두 배면 한 걸음 더, O(n) 은 두 배면 두 배.

하는 일Python최선의 경우평균의 경우최악의 경우더 드는 메모리언제 쓰나
리스트 맨 뒤에 넣기a.append(x)O(1)O(1)그 한 번은 O(n)(자리를 늘려 옮길 때), 나눠 내면 O(1)없음쌓아 가는 일은 늘 이것
리스트 맨 앞에 넣기a.insert(0, x)O(n)O(n)O(n)없음뒤의 칸을 모두 한 칸씩 밉니다. 양 끝에 자주 넣고 빼면 collections.deque
리스트에 값이 있나x in aO(1)O(n)O(n)없음한두 번이면 이것. 반복문 안에서 묻는다면 set 이나 dict 로
정렬된 칸에서 이진 탐색bisect.bisect_left(a, x)O(log n)O(log n)O(log n)없음이미 정렬돼 있고 순서도 필요할 때
dict 에서 찾기d[k], k in dO(1)O(1)O(n)(모든 키의 해시가 같을 때)dict 자체가 n 칸키로 여러 번 찾을 때
정렬sorted(a), a.sort()O(n)(이미 정렬됐거나 거꾸로일 때의 비교 수)O(n log n)O(n log n)sorted 는 새 리스트 n 칸한 번 정렬해 두고 여러 번 찾을 때. 방법은 기초 정렬, 병합·퀵 정렬

실험 ② 의 이진 탐색은 가운데 값이면 1 걸음에 멈추지만, bisect_left 는 값이 같아도 멈추지 않고 들어갈 자리를 끝까지 좁혀서 늘 log n 쯤 걸립니다. dict 가 왜 보통 O(1) 인지는 해시 테이블 쪽에서 봅니다.

8. Python 으로

실험 ② 의 이진 탐색을 그대로 옮기고 걸음을 셉니다.

def binary_search(cells, target):          # cells 는 작은 것부터 정렬돼 있다
    low, high, steps = 0, len(cells) - 1, 0
    while low <= high:
        middle = (low + high) // 2           # 남은 범위의 가운데 칸
        steps += 1
        if cells[middle] == target:
            return middle, steps
        if cells[middle] < target:
            low = middle + 1                 # 왼쪽 절반을 버린다
        else:
            high = middle - 1                # 오른쪽 절반을 버린다
    return -1, steps

cells = list(range(2, 2001, 2))              # 2, 4, ..., 2000 (1000칸)
print(binary_search(cells, 2000))            # (999, 10)
import bisect; print(bisect.bisect_left(cells, 2000))  # 999: 표준 라이브러리

어디에 쓰나

자주 묻는 것

빅오가 작은 쪽이 늘 더 빠른가요?

아닙니다. 빅오는 n 이 클 때 연산 횟수가 늘어나는 모양만 말합니다. 버린 상수와 작은 항은 n 이 작을 때 크게 남습니다. 칸이 몇 개뿐이면 O(n²) 인 단순한 방법이 O(n log n) 인 방법보다 빠를 수 있습니다. 실제 시간이 궁금하면 n 을 두 배씩 늘려 가며 재 봅니다.

dict 찾기는 왜 O(1) 인데 최악의 경우는 O(n) 인가요?

Python 문서의 dict 시간은 해시 값이 잘 겹치지 않는다고 가정한 보통의 값입니다. 그러면 칸이 아무리 많아도 몇 걸음 만에 찾습니다. 모든 키의 해시가 같은 최악의 경우는 겹친 것들을 하나씩 비교해야 해서 O(n) 이 됩니다.

append 는 가끔 전부 옮긴다는데 왜 O(1) 인가요?

리스트의 자리가 다 차면 더 큰 자리로 전부 옮깁니다. 그 한 번은 O(n) 이지만 자주 일어나지 않아서, 여러 번 넣은 전체 비용을 넣은 횟수로 나누면 한 번에 O(1) 입니다. 이것을 분할 상환(amortized)이라고 부릅니다. 한 번 한 번이 꼭 짧아야 하는 곳에서는 이 점을 기억합니다.

낱말

여기서 쓴 말책에서 부르는 말
걸음이 n 에 따라 늘어나는 모양시간 복잡도(time complexity), 증가 차수(order of growth)
빅오, 이보다 빨리 늘지는 않는다는 한계빅오 표기(Big O notation), 점근 표기(asymptotic notation)
더 드는 메모리의 모양공간 복잡도(space complexity)
그대로 · 한 걸음 더 · 두 배 · 두 배보다 조금 더 · 네 배 · 하나 늘면 두 배상수(constant) · 로그(logarithmic) · 선형(linear) · 선형 로그(linearithmic) · 제곱(quadratic) · 지수(exponential)
가장 나쁠 때 · 보통 · 가장 좋을 때최악(worst case) · 평균(average case) · 최선(best case)
나눠 내기분할 상환 분석(amortized analysis)
작은 항만 버린 근사물결표 근사(tilde approximation, ~)
앞에서부터 하나씩 찾기 · 반씩 잘라 찾기선형 탐색(linear search) · 이진 탐색(binary search)

출처

← AI 에이전트기초 정렬: 버블·선택·삽입 →