시간 복잡도

시간 복잡도는 입력이 커질 때 코드가 할 일이 얼마나 빨리 불어나는지 알려 줍니다. 시간을 초 단위로 재지 않습니다. 연산을 몇 번 하는지 세어서 그 횟수가 늘어나는 꼴을 봅니다. 컴퓨터 성능과 상관없이 데이터가 많아져도 버티는 방법을 미리 고를 수 있습니다.

상세

학교 출석부에서 이름 하나를 찾는다고 해 봅시다. 맨 윗줄부터 한 줄씩 내려가며 찾으면 학생이 두 배로 늘 때 찾는 시간도 두 배로 늡니다. 가나다순으로 적힌 출석부를 가운데부터 펴서 반씩 넘기면 학생이 두 배로 늘어도 한 번만 더 펴면 됩니다.

시간 복잡도는 이 차이를 적는 방법입니다. 코드나 알고리즘 하나가 비교나 덧셈 같은 기본 연산을 몇 번 하는지 입력 크기 n 의 함수로 셉니다. 그 함수가 n 을 따라 자라는 꼴을 봅니다. 몇 초 걸리는지는 묻지 않습니다.

이 절은 무엇을 세는지부터 정합니다. 그다음 센 값을 줄여 적는 법과 자주 만나는 꼴을 봅니다. 마지막으로 백엔드 코드에서 이 꼴이 드러나는 대목을 봅니다.

입력 크기와 기본 연산

시간 복잡도를 세려면 먼저 입력 크기를 정합니다. 목록의 원소 수, 문자열의 길이, 표의 행 수처럼 일의 양을 정하는 수입니다. 이 수를 n 이라고 둡니다.

다음으로 기본 연산을 정합니다. 값 두 개를 비교하거나 숫자 두 개를 더하는 것처럼 한 번에 끝나는 일입니다. 이런 일 하나는 입력이 커져도 걸리는 시간이 같다고 봅니다. 이 가정이 깨지는 경우는 뒤 「보장과 가정」 절이 다룹니다.

둘을 정하면 코드가 기본 연산을 몇 번 하는지 n 에 대한 식으로 적을 수 있습니다. 이 식을 흔히 T(n) 으로 씁니다. 목록에 든 수를 모두 더하는 코드는 덧셈을 n 번 합니다. 목록 안의 모든 값을 서로 한 번씩 비교하는 코드는 비교를 n(n−1)/2 번 합니다.

첫 값은 뒤의 n−1 개와 비교합니다. 둘째 값은 뒤의 n−2 개와 비교합니다. 이렇게 하나씩 줄어드니 모두 더하면 (n−1)+(n−2)+…+1, 곧 n(n−1)/2 번입니다. n 이 4 면 3+2+1 = 6 번입니다.

초 대신 횟수를 세는 까닭은 초가 컴퓨터마다 다르기 때문입니다. 같은 코드도 최신 서버에서는 짧게 걸리고 오래된 노트북에서는 길게 걸립니다. 횟수는 어느 컴퓨터에서 돌려도 같습니다. 횟수로 세면 방법끼리 견줄 잣대가 생깁니다.

빅오 표기법으로 줄여 적기

센 식은 줄여서 적습니다. 어떤 코드가 기본 연산을 3n² + 5n + 2 번 한다고 해 봅시다.

이 식에서 가장 빨리 자라는 항 하나만 남기고 그 앞의 상수도 떼어 냅니다. 그러면 n² 만 남습니다. 이것을 O(n²) 이라고 적습니다.

이렇게 줄여 적는 방식이 빅오 표기법입니다. O(n²) 은 「오 엔 제곱」이라고 읽습니다. 뜻은 n 이 충분히 커지면 연산 횟수가 n² 에 어떤 상수를 곱한 값을 넘지 않는다는 것입니다.

여기서 말하는 「어떤 상수」는 앞에서 떼어 낸 상수를 넉넉히 잡은 값입니다. 예를 들어 3n² + 5n + 2 는 n 이 6 이상이면 4n² 을 넘지 않습니다. 상수 4 를 곱한 n² 이 위에서 막아 주는 셈입니다. 빅오가 늘어나는 빠르기의 위쪽 한계를 적는다고 하는 까닭이 이것입니다.

작은 항을 버려도 되는 까닭은 n 이 커지면 그 항이 묻히기 때문입니다. 아래 표는 같은 식의 두 항을 n 에 따라 견준 것입니다.

n 이 10 이면 5n 도 무시 못 할 크기입니다. n 이 백만이면 5n 은 3n² 의 육십만분의 일밖에 안 됩니다.

앞에 붙은 상수 3 도 뗍니다. 3n² 이든 n² 이든 n 이 두 배가 되면 네 배로 늘어납니다. 상수는 값을 몇 배로 키울 뿐 늘어나는 꼴을 바꾸지 않습니다.

자주 만나는 꼴

실무에서 만나는 시간 복잡도는 대부분 몇 가지 꼴 안에 듭니다. 아래 표는 느리게 자라는 꼴부터 차례로 놓았습니다. 가운데 칸은 n 이 1,000 일 때 연산 횟수가 대략 몇 번인지 보입니다.

표 첫 줄의 해시테이블은 키에서 번호를 계산해 그 번호의 칸에 값을 넣고 꺼내는 자료구조입니다. 키로 바로 그 칸을 찾아가므로 값 하나를 꺼내는 횟수가 원소 수를 따라 늘지 않습니다.

표에서 해시테이블 뒤에 붙은 「평균」은 입력에 따라 연산 횟수가 갈린다는 표시입니다. 같은 코드도 들어오는 입력에 따라 하는 일이 달라집니다.

일이 가장 많아지는 입력을 기준으로 센 값은 최악의 경우입니다. 입력이 고르게 들어온다고 보고 평균을 낸 값은 평균의 경우입니다. 두 기준은 뒤 「갈래」 절에서 하나씩 봅니다.

O(log n) 은 남은 일을 한 번에 절반씩 버리는 코드에서 나옵니다. 1,000 을 계속 반으로 나누면 열 번쯤에 하나가 남습니다. n 이 백만으로 늘어도 스무 번이면 끝납니다. 이때의 로그는 밑이 2 인 로그 함수입니다.

표의 위쪽 꼴과 아래쪽 꼴은 n 이 커질수록 차이가 벌어집니다. n 이 두 배가 되면 O(n) 은 일이 두 배가 되고 O(n²) 은 네 배가 됩니다.

아래 그림은 n 을 1부터 10까지 늘리며 두 꼴의 연산 횟수를 그린 것입니다. 완만하게 오르는 선이 n 입니다. 가파르게 치솟는 선이 n² 입니다.

xychart-beta
    title "n 과 n² 의 연산 횟수"
    x-axis "입력 크기 n" [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    y-axis "연산 횟수" 0 --> 100
    line [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    line [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

백엔드 코드에서 드러나는 꼴

백엔드 개발자가 시간 복잡도를 가장 자주 만나는 때는 데이터가 늘었을 때입니다. 개발 환경의 데이터 백 건에서는 O(n) 과 O(n²) 의 차이가 거의 안 보입니다. 운영 데이터가 십만 건이 되면 O(n) 은 십만 번 연산합니다. O(n²) 은 백억 번 규모로 불어납니다.

아래 두 함수는 목록에 같은 값이 두 번 들어 있는지 확인합니다. 하는 일은 같고 시간 복잡도만 다릅니다.

def has_dup_pairs(items):   # O(n²)
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] == items[j]:
                return True
    return False

def has_dup_set(items):     # 평균 O(n)
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

has_dup_pairs([3, 1, 4, 1])  # True
has_dup_set([3, 1, 4, 1])    # True

앞의 함수는 반복문 안에 반복문을 두어 모든 쌍을 견줍니다. 그래서 O(n²) 입니다. 뒤의 함수는 한 번 본 값을 집합에 넣어 둡니다. 새 값이 오면 거기 있는지만 확인합니다.

이 코드의 set 은 해시테이블로 만든 집합입니다. 그래서 확인 한 번이 평균 O(1) 입니다. 목록은 한 번만 훑으므로 전체는 평균 O(n) 입니다.

대신 뒤의 함수는 본 값을 담아 둘 메모리를 더 씁니다. 메모리가 입력에 따라 얼마나 느는지 재는 잣대는 공간 복잡도입니다.

시간을 줄이려고 메모리를 더 쓰는 이런 선택이 시간과 공간 맞바꿈입니다.

데이터베이스 조회도 같은 눈으로 볼 수 있습니다. 인덱스는 한 열의 값을 따로 정리해 둔 찾아보기용 구조입니다. 인덱스가 없는 열로 행을 찾으면 표 전체를 훑어야 해서 O(n) 입니다.

인덱스를 만드는 대표적인 구조가 B-tree 입니다. B-tree 는 값을 여러 단계로 나눠 정리해 둡니다. 위 단계에서 아래 단계로 한 번 내려갈 때마다 살펴볼 후보가 크게 줄어듭니다. 이진 탐색이 절반씩 버리는 것과 같은 이치라 O(log n) 으로 찾습니다.

배경

튜링 기계는 칸이 이어진 테이프에 기호를 하나씩 읽고 쓰는 계산 모형입니다. 튜링은 이 모형으로 기계적 절차가 계산할 수 있는 수열과 없는 수열을 갈랐습니다. 그런데 계산할 수 있는 쪽 안에서도 아주 쉽게 계산되는 것과 본디 어려워 보이는 것이 섞여 있었습니다.

이 차이를 수로 적어 가를 방법이 필요했습니다. 그 수는 시간 단위나 기계 부품의 속도에 따라 바뀌면 안 됩니다. 초로 잰 시간은 기계를 이루는 부품이 빠르면 줄고 느리면 늡니다. 같은 계산의 어려움이 기계마다 다른 값으로 적히는 셈입니다.

1965년 하트마니스(Hartmanis)와 스턴스(Stearns)는 초 대신 연산 수를 셌습니다. 테이프가 여러 개인 튜링 기계가 수열의 앞 n 개를 T(n) 번을 넘지 않는 연산으로 적어 낼 수 있는지를 따졌습니다. 이 상한 함수 T(n) 을 time-function(시간 함수)이라 불렀습니다.

여기서 n 은 수열의 앞에서 몇 개를 적어 내는지를 세는 수입니다. 코드에서 입력 크기가 하는 몫을 이 모형에서는 이 수가 맡습니다.

T(n) 안에 계산되는 수열들은 복잡도 클래스(complexity class)라는 한 부류로 묶었습니다. T(n) 에 양수 k 를 곱해도 같은 부류가 나온다는 속도 향상 정리(speed-up theorem)도 보였습니다. 기계 부품이 k 배 빨라지는 것은 같은 계산의 상한에 k 를 곱하거나 나누는 것과 같습니다. 그 곱셈이 부류를 바꾸지 않으므로 이 잣대는 시간 단위나 부품 속도와 무관합니다.

두 사람이 쓴 이름은 computational complexity(계산 복잡도)와 time-function, complexity class 였습니다. 「time complexity」라는 이름이 언제 굳었는지는 원 논문에 없습니다(미확인).

예시

시간 복잡도는 제품 문서와 언어 표준에 계약처럼 적혀 있습니다. 아래 여섯은 키-값 저장소, 언어 표준 라이브러리, 보안 연구에서 이 잣대가 쓰인 실물입니다.

Redis 의 KEYS 명령

Redis 는 키와 값을 짝지어 두는 키-값 저장소입니다. 키 이름을 패턴으로 찾는 KEYS 명령의 문서 머리에는 시간 복잡도 칸이 있습니다.

Time complexity:
O(N) with N being the number of keys in the database, under the assumption that the key names in the database and the given pattern have limited length.

N 은 데이터베이스에 든 키 전체의 개수입니다. 패턴에 맞는 키가 몇 개든 연산 횟수는 키 전체의 개수를 따라 늘어난다는 뜻입니다. 뒤에 붙은 단서는 키 이름과 패턴의 길이가 제한돼 있다고 가정한 값이라는 것입니다.

O(N) 앞에 붙는 상수는 꽤 작습니다. 보급형 노트북에서 도는 Redis 는 키 백만 개짜리 데이터베이스를 40밀리초에 훑을 수 있습니다. 그래도 큰 데이터베이스에 실행하면 성능을 망칠 수 있습니다. 그래서 운영 환경에서는 아주 조심해서 쓰라는 경고가 붙어 있습니다.

KEYS 는 디버깅이나 키 배치를 바꾸는 작업 같은 특수한 용도의 명령입니다. 일반 애플리케이션 코드에는 쓰지 말라고 합니다. 키 일부를 찾을 때는 SCAN 이나 집합(set)을 대신 쓰는 방법을 권합니다. 상수가 작아도 N 은 키 전체입니다. 데이터베이스가 커지면 한 번의 실행도 함께 길어집니다.

Java 의 HashMap

HashMap 은 Java 표준 라이브러리의 해시테이블입니다. 해시테이블은 키에서 번호를 계산해 그 번호의 칸에 값을 넣습니다. 이 칸은 버킷입니다. 번호를 계산하는 함수는 해시 함수입니다.

HashMap 의 기본 연산인 get 과 put 은 상수 시간입니다. 단서가 붙습니다.

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

해시 함수가 원소를 버킷에 고르게 흩는다고 가정할 때만 상수 시간이라는 뜻입니다.

전체를 훑는 비용은 따로 정해져 있습니다. 훑는 시간은 버킷 수(capacity)에 원소 수(size)를 더한 값에 비례합니다. 훑기 성능이 중요하면 처음 버킷 수를 너무 크게 잡지 않습니다. 원소가 적어도 버킷이 많으면 빈 칸까지 훑기 때문입니다.

JEP 180 — HashMap 의 충돌 대책

JEP(JDK Enhancement Proposal) 180 은 자바 개발 키트(Java Development Kit, JDK)의 개선 제안입니다. 이 제안은 해시 충돌이 잦을 때의 HashMap 을 고쳤습니다. 해시 충돌은 서로 다른 키가 같은 버킷으로 가는 일입니다. 제안은 Java 8 에 들어갔습니다.

충돌이 나면 한 버킷에 원소가 여럿 매달립니다. 이 제안 전에는 그 원소들을 연결 리스트로 담았습니다. 연결 리스트는 원소마다 다음 원소를 가리켜 한 줄로 잇는 구조입니다. 값을 찾으려면 줄을 앞에서부터 따라가야 합니다.

제안 뒤에는 한 버킷의 원소 수가 제안이 정한 기준을 넘으면 그 버킷이 원소를 균형 트리로 담습니다. 균형 트리는 한쪽으로 기울지 않게 높이를 맞춰 두는 트리입니다. 충돌이 심할 때 최악의 경우 시간이 O(n) 에서 O(log n) 으로 줄어듭니다.

아래 그림은 한 버킷에 원소 일곱 개가 매달린 두 모양입니다. 위는 제안 전의 연결 리스트라 마지막 원소를 보려면 줄을 일곱 칸 따라가야 합니다. 아래는 제안 뒤의 균형 트리라 세 층만 내려가면 됩니다.

flowchart TD
    subgraph chain["제안 전 · 연결 리스트"]
        CB["버킷 1"] --> C1["원소 1"] --> C2["원소 2"] --> C3["원소 3"] --> C4["원소 4"] --> C5["원소 5"] --> C6["원소 6"] --> C7["원소 7"]
    end
    subgraph tree["제안 뒤 · 균형 트리"]
        TB["버킷 1"] --> T4["원소 4"]
        T4 --> T2["원소 2"]
        T4 --> T6["원소 6"]
        T2 --> T1["원소 1"]
        T2 --> T3["원소 3"]
        T6 --> T5["원소 5"]
        T6 --> T7["원소 7"]
    end
    chain ~~~ tree

대가는 균형 트리를 만들고 관리하는 부담입니다. 제안은 그 부담이 무시할 만할 것으로 내다봤습니다. LinkedHashMap 에도 같은 개선이 들어갔습니다.

알고리즘 복잡도 공격

2003년 크로스비(Crosby)와 월랙(Wallach)은 시간 복잡도의 평균과 최악 사이의 틈을 노리는 서비스 거부(Denial of Service, DoS) 공격을 발표했습니다. 서비스 거부 공격은 서버가 정상 요청을 처리하지 못하게 만드는 공격입니다.

흔히 쓰는 자료구조는 평균의 경우 시간이 최악의 경우보다 훨씬 짧습니다. 그런데 이진 트리와 해시테이블은 골라 만든 입력이 들어오면 연결 리스트처럼 퇴화할 수 있습니다. 두 사람은 그런 입력을 공격자가 계산해 낼 수 있음을 보였습니다. 공격 대상은 프로그래밍 언어 Perl 두 판의 해시테이블 구현, 웹 프록시 Squid, 침입 탐지 시스템 Bro 였습니다.

보통의 전화 접속 모뎀보다 좁은 대역폭으로 Bro 전용 서버를 무너뜨릴 수 있음을 보였습니다. 골라 만든 패킷을 6분 보낸 뒤 그 서버는 트래픽을 최대 71%까지 놓쳤습니다. CPU(Central Processing Unit, 중앙 처리 장치)도 모두 썼습니다.

대책으로는 범용 해싱(universal hashing)을 들었습니다. 범용 해싱은 해시 함수 하나를 미리 정해 두지 않고 여러 함수 가운데서 무작위로 골라 씁니다. 그래서 공격자가 어느 키끼리 충돌할지 미리 계산하기 어렵습니다.

범용 해싱은 흔한 해시 함수와 견줄 만한 성능을 낼 수 있습니다. 그러면서도 이 공격에 안전하다는 것을 증명할 수 있습니다.

C++ 의 std::sort

C++ 표준 라이브러리의 std::sort 는 정렬할 원소 수를 N 이라 할 때 비교를 O(N·log N) 번 하도록 요구받습니다.

Given N as last - first:
𝓞(N·log(N)) comparisons

이 요구가 처음부터 이랬던 것은 아닙니다. C++ 표준 라이브러리 작업 그룹(Library Working Group, LWG)의 이슈 713 이 고치기 전에는 퀵 정렬만으로 구현해도 됐습니다. 퀵 정렬은 기준 값 하나를 골라 그보다 작은 쪽과 큰 쪽으로 나눈 뒤 양쪽을 다시 정렬하는 방법입니다. 최악의 경우 비교를 O(N²) 번 할 수 있습니다.

sort() 구현에는 대개 인트로 정렬(introsort)을 씁니다. 인트로 정렬은 퀵 정렬로 시작합니다. 나누는 단계가 정해 둔 깊이를 넘으면 다른 정렬 방법으로 갈아탑니다. 갈아타는 정렬이 무엇이고 그 깊이가 얼마인지는 미확인입니다.

인트로 정렬은 이렇게 해서 모든 경우를 O(N·log N) 비교로 처리합니다. 평균의 경우에 부담을 더 얹지도 않습니다.

요구가 바뀌어도 구현이 바로 따라오지는 않습니다. C++ 표준 라이브러리 구현의 하나인 libc++ 는 14판 전까지 고친 시간 복잡도 요구를 구현하지 않았습니다.

CPython 의 list 와 dict

CPython 은 파이썬의 표준 구현입니다. python.org 위키에 CPython 의 연산별 시간 복잡도 표가 있습니다. 아래는 그 표에서 고른 행입니다. n 은 컨테이너에 지금 든 원소 수입니다.

오른쪽 칸의 분할 상환은 연산을 여러 번 이어 할 때 한 번당 비용으로 센 값입니다. 뒤 「갈래」 절에서 다룹니다.

list 는 안에서 배열로 표현됩니다. 그래서 중간에 넣거나 빼면 그 뒤의 원소를 모두 옮겨야 합니다. 중간의 k 번째 원소를 빼면 n − k 개를 옮기므로 O(n − k) 입니다.

dict 의 평균 O(1) 에는 가정이 붙습니다. 해시 함수가 충돌을 드물게 만들 만큼 튼튼해야 합니다. 조회에 쓰는 키도 모든 키 가운데서 고르게 무작위로 골랐다고 봅니다. 오른쪽 칸의 O(n) 은 분할 상환 최악의 경우 값입니다.

문자열 키만 다루는 dict 에는 전용 경로(fast-path)가 따로 있습니다. 이 경로는 시간 복잡도를 바꾸지 않습니다. 대신 상수 배수를 크게 바꿀 수 있습니다. 보통 프로그램이 얼마나 빨리 끝나는지가 그 상수 배수에 달려 있습니다.

다른 파이썬 구현이나 다른 판의 CPython 은 성능 특성이 조금 다를 수 있습니다. 그래도 대개 O(log n) 배 넘게 더 걸리지는 않는다고 봐도 됩니다.

갈래

같은 코드라도 어떤 입력이 들어오느냐에 따라 할 일이 달라집니다. 목록을 앞에서부터 훑어 값을 찾는 코드는 찾는 값이 맨 앞에 있으면 한 번에 끝납니다. 맨 뒤에 있거나 아예 없으면 n 번을 다 봐야 합니다.

그래서 시간 복잡도를 말할 때는 어느 입력을 기준으로 셌는지를 함께 정합니다. 갈래를 가르는 축은 이 기준입니다. 입력 하나를 고르는 셋(최악·평균·최선)과, 연산을 여러 번 이어 한 묶음을 기준으로 삼는 분할 상환이 있습니다.

최악의 경우

일이 가장 많아지는 입력을 기준으로 센 값입니다. 어떤 입력이 와도 이 횟수를 넘지 않는다는 약속이 됩니다. 따로 말이 없으면 시간 복잡도는 대개 최악의 경우를 가리킵니다.

입력을 고르는 쪽이 공격자라면 최악의 경우가 곧 겪는 경우가 됩니다. 해시테이블은 평균 O(1) 입니다. 키가 한 버킷에 몰려 줄지어 매달리면 그 줄을 끝까지 따라가야 해서 O(n) 이 됩니다. 예시 절의 알고리즘 복잡도 공격이 이 틈을 노렸습니다.

평균의 경우

입력이 고르게, 곧 무작위로 들어온다고 보고 평균을 낸 값입니다. 해시테이블이 이 갈래를 보이는 대표입니다. 서로 다른 키가 같은 버킷으로 가면 그 버킷 아래에 키가 줄지어 매달립니다. 키가 버킷마다 고르게 흩어지면 줄이 짧아서 조회가 평균 O(1) 입니다.

아래 그림은 버킷 네 개에 키 네 개가 들어간 두 경우입니다. 위는 키가 고르게 흩어져 버킷마다 하나씩 매달렸습니다. 이것이 평균의 경우가 가정하는 모양입니다. 아래는 키가 한 버킷에 몰려 줄이 길어졌습니다. 그 줄을 끝까지 따라가야 하는 이 모양이 최악의 경우입니다.

flowchart TD
    subgraph even["키가 고르게 흩어짐"]
        A0["버킷 0"] --> K1["키 1"]
        A1["버킷 1"] --> K2["키 2"]
        A2["버킷 2"] --> K3["키 3"]
        A3["버킷 3"] --> K4["키 4"]
    end
    subgraph skew["키가 한 버킷에 몰림"]
        B0["버킷 0"]
        B1["버킷 1"] --> L1["키 1"] --> L2["키 2"] --> L3["키 3"] --> L4["키 4"]
        B2["버킷 2"]
        B3["버킷 3"]
    end
    even ~~~ skew

최선의 경우

일이 가장 적어지는 입력을 기준으로 센 값입니다. 앞에서부터 훑는 찾기라면 찾는 값이 맨 앞에 있을 때 한 번입니다. 이 값은 다른 입력이 왔을 때 무엇도 약속하지 않습니다. 그래서 코드를 고르는 잣대로는 잘 쓰지 않습니다.

CPython 의 list 에서 중간 원소를 빼는 연산이 세 경우를 한꺼번에 보입니다. 끝에서 둘째 원소를 빼면 하나만 옮기는 최선의 경우입니다. 첫 원소를 빼면 n − 1 개를 옮기는 최악의 경우입니다. 가운데를 빼는 평균의 경우는 O(n/2), 곧 O(n) 입니다.

분할 상환

연산 하나가 아니라 연산을 여러 번 이어 한 묶음을 기준으로 셉니다. 묶음 전체의 비용을 연산 수로 나눈 값입니다. 시간에 걸쳐 고르게 펴서 평균을 내는 셈입니다. 평균의 경우와 달리 입력이 무작위라고 가정하지 않습니다. 1985년 타잔(Tarjan)이 이 잣대를 다룬 여러 연구를 묶어 정리했습니다.

CPython 의 list 에 끝에 붙이기를 거듭하는 경우가 그 예입니다. 대부분은 바로 끝납니다. 그런데 미리 잡아 둔 크기를 넘는 순간에는 원소를 모두 새 공간으로 옮겨야 합니다. 한 번의 붙이기가 놀랄 만큼 오래 걸릴 수 있습니다.

그래도 이어 한 붙이기 전체로 나누면 한 번당 O(1) 입니다. 이 값이 표의 「분할 상환 최악의 경우」 칸입니다.

보장과 가정

시간 복잡도가 약속하는 것은 하나입니다. n 이 충분히 커지면 기본 연산 횟수가 c·f(n) 을 넘지 않는다는 것입니다. 여기서 f(n) 은 n² 같은 꼴입니다. c 는 어떤 상수입니다.

이것이 실행 시간에 대한 약속으로 이어지려면 몇 가지 가정이 서 있어야 합니다.

기본 연산 한 번이 상수라는 가정

빅오로 적은 식은 기본 연산 한 번을 비용 1 로 칩니다. 기본 연산 한 번의 비용을 식에 드러내 적은 계산 모형이 랜덤 액세스 기계(Random Access Machine, RAM)입니다. 이름이 같지만 메모리 칩을 가리키는 RAM 과는 다른 것입니다.

이 모형에서는 정수 하나를 담는 칸인 레지스터가 끝없이 이어져 있습니다. 유한한 프로그램이 그 레지스터들을 읽고 씁니다.

1973년 쿡(Cook)과 렉하우(Reckhow)는 이 모형에서 명령 하나의 실행 시간을 l(n) 으로 두었습니다. l(n) 은 명령이 다루는 수가 얼마나 큰지로 정해지는 함수입니다. 여기서 n 은 입력 크기가 아니라 명령이 다루는 그 수 자체입니다.

가장 자연스러운 값은 둘입니다. l(n) 을 늘 1 로 두면 수가 아무리 커도 기본 연산 한 번입니다. l(n) 을 대략 log |n| 으로 두면 큰 수일수록 한 번의 비용이 커집니다.

워드는 기계가 한 번에 다루는 수의 단위입니다. 워드 크기가 정해진 기계에서 큰 수를 담으려면 워드를 여러 개 써야 합니다. 뒤의 값은 그렇게 드는 워드 수만큼 비용을 매기는 것과 같습니다.

두 사람은 특정 알고리즘의 결과를 말할 때 이런 가정을 드러내 적는 편이 바람직할 때가 많다고 봤습니다.

예시 절의 Redis KEYS 에 붙은 단서가 이 가정을 적은 것입니다. 「키 이름과 패턴의 길이가 제한돼 있다고 가정하면」은 키 하나를 패턴과 맞춰 보는 일을 기본 연산 한 번으로 친다는 뜻입니다. 키 이름이 끝없이 길어질 수 있다면 그 한 번의 비용도 길이를 따라 늘어납니다.

계산 모형이라는 가정

같은 계산도 어떤 기계로 세느냐에 따라 식이 바뀝니다. 모형 둘을 짝지어 보면 그 가운데 일부는 제곱 관계로 이어져 있습니다. 테이프가 여러 개인 튜링 기계가 T(n) 안에 계산하는 것은 테이프가 하나뿐인 튜링 기계로 T(n)² 안에 계산할 수 있습니다. 이 한 쌍이 그런 예입니다.

식을 적을 때 어느 모형에서 셌는지가 함께 서 있어야 하는 까닭이 이것입니다. 앞 소절의 랜덤 액세스 기계가 그렇게 밝혀 둔 모형 하나입니다. 실무에서 적는 복잡도는 대개 기본 연산 한 번을 상수로 보는 이 모형을 깔고 있습니다.

입력이 고르게 들어온다는 가정

평균의 경우로 적은 값은 입력이 고르게 들어온다는 가정 위에 섭니다. Java HashMap 의 상수 시간에는 「해시 함수가 원소를 버킷에 고르게 흩는다고 가정하면」이라는 단서가 붙습니다. 키가 한 버킷에 몰리면 이 단서가 깨집니다. 공격자가 그런 키를 골라 보내면 가정은 저절로 깨집니다.

가정이 깨진 뒤의 최악은 몰린 버킷을 어떻게 담느냐에 달려 있습니다. 원소를 연결 리스트로 매달아 두는 구현이라면 조회가 O(n) 으로 늘어납니다. 예시 절의 JEP 180 처럼 균형 트리로 바꾸는 구현이라면 O(log n) 입니다.

입력이 크다는 가정

빅오는 n 이 충분히 클 때의 약속입니다. 입력이 작으면 버린 상수가 순서를 정합니다. O(n log n) 정렬이라도 앞에 붙은 상수가 크면, 원소가 몇십 개일 때는 O(n²) 인 단순한 정렬보다 오래 걸릴 수 있습니다.

병합 정렬을 짤 때 이 점을 쓰기도 합니다. 병합 정렬은 목록을 반씩 쪼갠 뒤 다시 합치며 정렬합니다. 쪼갠 조각이 작아지면 거기서부터는 삽입 정렬로 그 조각을 정리하게 짤 수 있습니다.

삽입 정렬은 원소를 하나씩 꺼내 앞쪽의 정렬된 부분에서 알맞은 위치에 끼워 넣는 정렬입니다. 시간 복잡도는 O(n²) 입니다. 조각이 작으면 버린 상수가 순서를 정하므로 이 O(n²) 쪽이 덜 걸립니다.

메모리를 읽는 비용이 같다는 가정

메모리를 읽는 방식도 식에 들어가지 않습니다. 같은 O(n) 이라도 배열처럼 붙어 있는 메모리를 차례로 읽는 코드는 연결 리스트처럼 흩어진 메모리를 따라가는 코드보다 덜 걸리는 경우가 많습니다. 가까운 메모리를 이어 읽을 때 시간이 줄어드는 이 성질이 캐시 지역성입니다.

꼴을 보는 때와 재는 때

가정이 깨질 수 있으므로 시간 복잡도는 방법을 고르는 첫 잣대로 씁니다. 걸리는 시간은 따로 잽니다. 사용자 목록이나 로그처럼 계속 쌓이는 데이터를 다루는 코드라면 꼴을 먼저 봅니다. 입력이 늘 작게 정해져 있다면 꼴보다 잰 값이 더 믿을 만합니다.

코드의 어느 부분이 시간을 먹는지 재는 일을 프로파일링이라고 합니다. 여러 방법의 시간을 같은 조건에서 재어 견주는 일은 벤치마크입니다.

관련 항목

시간 복잡도를 적는 표기법

빅오 표기법 · 빅세타 표기법 · 빅오메가 표기법 · 점근 표기법 · 점근 분석

시간 복잡도와 함께 따지는 비용 지표

공간 복잡도 · 시간과 공간 맞바꿈 · 분할 상환 비용

시간 복잡도를 셀 때 고르는 입력 기준

최악의 경우 · 평균의 경우 · 최선의 경우 · 분할 상환 분석 · 재귀 관계식

시간 복잡도를 세는 계산 모형

튜링 기계 · 다중 테이프 튜링 기계 · 랜덤 액세스 기계 · 단위 비용 모형 · 로그 비용 모형 · 속도 향상 정리

시간 복잡도로 가르는 문제의 부류

복잡도 클래스 · P 대 NP 문제 · 다항 시간 · NP-완전

시간 복잡도로 견주는 알고리즘과 자료구조

알고리즘 · 자료구조 · 이진 탐색 · 순차 탐색 · 완전 탐색 · 분할 정복 · 정렬 · 정렬 알고리즘 · 병합 정렬 · 삽입 정렬 · 선택 정렬 · 퀵 정렬 · 인트로 정렬 · 해시테이블 · 해시 충돌 · 해시 함수 · B-tree · 인덱스 · 배열 · 동적 배열 · 연결 리스트 · 균형 이진 탐색 트리 · 이진 탐색 트리 · 집합 · 그래프

시간 복잡도를 계약으로 적은 제품과 문서

Redis · KEYS · SCAN · Java · HashMap · LinkedHashMap · JEP 180 · C++ · libc++ · CPython · 파이썬

최악의 경우를 노리는 공격과 그 대책

알고리즘 복잡도 공격 · 서비스 거부 공격 · 해시 플러딩 · 범용 해싱

시간 복잡도가 못 재는 시간을 재는 수단

프로파일링 · 프로파일러 · 벤치마크 · 성능 테스트 · 부하 테스트 · 응답 시간

시간 복잡도 식에 안 잡히는 메모리 비용

캐시 지역성 · CPU 캐시 · 캐시 라인 · 캐시 미스 · 메모리 계층 구조

이것이 속하는 상위 분류

계산 복잡도 이론 · 알고리즘 분석 · 계산 가능성 이론 · 성능

시간 복잡도 식을 이루는 수학 함수

로그 함수 · 지수 함수 · 다항식 · 극한