시간 복잡도

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

상세

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

시간 복잡도는 이 차이를 적는 방법입니다. 코드나 알고리즘 하나가 몇 초 걸리는지는 묻지 않습니다. 다룰 데이터가 늘어날 때 할 일이 어떤 꼴로 늘어나는지를 묻습니다.

이 절은 먼저 무엇을 세는지 정합니다. 그다음 센 값을 줄여 적는 법과 자주 만나는 꼴을 봅니다. 마지막으로 백엔드 코드에서 이 차이가 드러나는 대목과, 시간 복잡도가 알려 주지 않는 것을 봅니다.

입력 크기와 기본 연산

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

다음으로 기본 연산을 정합니다. 값 두 개를 비교하거나 숫자 두 개를 더하는 것처럼 한 번에 끝나는 일입니다. 이런 일 하나는 입력이 커져도 걸리는 시간이 같다고 봅니다.

둘을 정하면 코드가 기본 연산을 몇 번 하는지 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]

같은 코드도 입력에 따라 갈리는 시간

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

시간 복잡도를 말할 때는 어느 경우인지를 함께 정합니다. 일이 가장 많아지는 입력을 기준으로 잡은 것이 최악의 경우입니다. 입력이 고르게 들어온다고 보고 평균을 낸 것은 평균의 경우입니다. 따로 말이 없으면 대개 최악의 경우를 가리킵니다.

해시테이블이 두 경우가 갈리는 대표적인 예입니다. 해시테이블은 키마다 들어갈 칸을 계산해 그 칸에 값을 넣습니다. 키를 찾을 때도 칸을 계산해 곧장 그 칸으로 갑니다.

서로 다른 키가 같은 칸으로 가는 일을 해시 충돌이라고 합니다. 충돌이 나면 그 칸 아래에 키를 줄지어 매달아 두는 방법을 흔히 씁니다. 키가 여러 칸에 고르게 흩어지면 칸마다 매달린 키가 적어서 조회는 평균 O(1) 입니다. 키가 한 칸에 몰리면 그 줄을 끝까지 따라가야 해서 최악에는 O(n) 이 됩니다.

아래 그림은 칸 네 개에 키 네 개가 들어간 두 경우입니다. 위는 키가 고르게 흩어져 칸마다 하나씩 매달렸습니다. 아래는 키가 한 칸에 몰려 줄이 길어졌습니다.

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

백엔드 코드에서 드러나는 대목

백엔드 개발자가 시간 복잡도를 가장 자주 만나는 때는 데이터가 늘었을 때입니다. 개발 환경의 데이터 백 건에서는 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) 으로 찾습니다.

시간 복잡도가 알려 주지 않는 것

시간 복잡도는 늘어나는 꼴만 봅니다. 버린 상수와 작은 항이 중요한 상황에서는 답을 주지 못합니다.

입력이 작을 때가 그렇습니다. O(n log n) 정렬이라도 앞에 붙은 상수가 크면, 원소가 몇십 개일 때는 O(n²) 인 단순한 정렬보다 오래 걸릴 수 있습니다.

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

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

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

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

관련 항목

시간 복잡도를 적는 표기법

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

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

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

입력에 따라 갈리는 분석 기준

최악의 경우 · 평균의 경우 · 최선의 경우 · 재귀 관계식

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

알고리즘 · 자료구조 · 이진 탐색 · 정렬 · 병합 정렬 · 삽입 정렬 · 해시테이블 · 해시 충돌 · B-tree · 배열 · 연결 리스트 · 그래프 · 집합

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

프로파일링 · 벤치마크 · 응답 시간 · 캐시 지역성 · 성능

이것이 속하는 상위 분류

계산 복잡도 이론 · 알고리즘 분석 · P 대 NP 문제

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

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