점근 분석

점근 분석은 입력이 아주 커졌을 때 어느 알고리즘이 버티는지를 가려 줍니다. 비용을 초로 재지 않고 입력 크기에 대한 식으로 세웁니다. 그 식에서 작은 부분은 버리고 가장 빨리 불어나는 꼴 하나만 봅니다. 그래서 컴퓨터를 바꿔도 달라지지 않는 비교가 나옵니다.

상세

멀리 있는 산을 바라본다고 해 봅시다. 가까이 다가가면 바위와 나무가 하나하나 보입니다. 멀리 물러날수록 작은 굴곡은 지워지고 큰 능선만 남습니다.

점근 분석은 알고리즘의 비용을 이렇게 멀리서 봅니다. 입력 크기를 n 이라고 둡니다. 그리고 n 이 한없이 커질 때 비용이 어떤 꼴로 불어나는지만 봅니다. 이 꼴을 증가 차수(order of growth)라고 합니다.

이름의 「점근」은 점점 가까워진다는 뜻입니다. 그래프가 끝없이 다가가는 직선을 점근선이라고 부를 때와 같은 말입니다. 수학에서는 함수가 끝으로 갈 때의 모양을 다루는 방법을 두루 이렇게 부릅니다. 컴퓨터 과학에서는 주로 알고리즘의 비용을 비교하는 데 씁니다.

이 방법이 필요한 이유는 둘입니다. 먼저, 초로 잰 시간은 컴퓨터와 언어에 따라 달라서 방법끼리 비교하는 기준이 못 됩니다. 다음으로, 입력 크기마다 다 돌려 볼 수는 없습니다. 식 하나로 모든 크기를 한꺼번에 말해야 합니다.

이 절은 먼저 비용을 n 의 식으로 세우고 그 식을 줄이는 법을 봅니다. 그다음 줄인 결과를 적는 세 표기와, 자기 자신을 부르는 코드에 쓰는 법을 봅니다. 끝으로 시간 밖으로 넓혀 쓰는 법과 점근 분석이 가리는 비용을 봅니다.

비용을 입력 크기의 식으로 세우기

첫 단계는 입력 크기 n 을 정하는 것입니다. 목록의 원소 수나 문자열의 길이처럼 일의 양을 정하는 수입니다. 다음으로 비교나 덧셈처럼 한 번에 끝나는 일을 기본 연산으로 정합니다.

그러면 코드가 기본 연산을 몇 번 하는지 n 에 대한 식으로 적을 수 있습니다. 이 식을 흔히 T(n) 이라고 부릅니다. T 는 시간을 뜻하는 영어 time 의 첫 글자입니다.

아래 함수는 기본 연산을 할 때마다 ops 를 하나씩 올려 횟수를 셉니다. 반복문 안의 반복문이 n² 번 돌고, 뒤의 반복문이 n 번 돕니다.

def count_ops(n):
    ops = 0
    for i in range(n):
        for j in range(n):
            ops += 1
    for i in range(n):
        ops += 1
    return ops

count_ops(10)     # 110
count_ops(1000)   # 1001000

이 함수의 T(n) 은 n² + n 입니다. n 이 10 이면 100 에 10 을 더한 110 이 나옵니다.

가장 빨리 자라는 항 하나

위 식에서 n 이 1,000 일 때 n² 부분은 1,000,000 이고 n 부분은 1,000 입니다. 뒤쪽은 전체의 천분의 일도 안 됩니다. n 이 커질수록 이 비율은 더 작아집니다.

점근 분석은 가장 빨리 자라는 항 하나만 남기고 나머지 항을 버립니다. n² + n 은 n² 이 됩니다. 3n² + 5n + 7 같은 식도 n² 꼴로 봅니다.

앞에 곱한 상수, 곧 계수도 뗍니다. 3n² 과 n² 은 n 이 두 배가 되면 둘 다 네 배가 됩니다. 계수는 값을 몇 배로 키울 뿐 불어나는 꼴은 바꾸지 않습니다.

계수를 떼는 이유가 하나 더 있습니다. 같은 코드라도 기계나 언어에 따라 기본 연산 하나에 드는 시간이 다릅니다. 그 차이는 결국 계수에 섞여 들어갑니다. 계수를 떼면 기계마다 달라지는 부분이 함께 빠집니다.

이렇게 남는 꼴은 몇 가지로 모입니다. 느리게 자라는 쪽부터 놓으면 1 · log n · n · n log n · n² · 2ⁿ 입니다. 비용을 시간으로 잰 이 꼴을 시간 복잡도라고 부릅니다. 꼴마다 어떤 코드가 나오는지는 그 항목이 다룹니다.

맨 앞의 1 은 n 이 커져도 비용이 늘지 않는 꼴입니다. 이것을 상수 꼴이라고 부릅니다.

log n 은 n 을 몇 번 반으로 나눠야 1 이 되는지를 세는 수입니다. n 이 1,000 이면 열 번쯤입니다. 백만이어도 스무 번쯤입니다.

어느 크기부터 뒤집히지 않는 순서

두 방법의 비용이 100n 과 n² 이라고 해 봅시다. 100n 은 계수가 큽니다. n² 은 계수가 작지만 더 빨리 자랍니다.

n 이 100 보다 작으면 n² 쪽이 덜 듭니다. n 이 10 이면 100n 은 1,000 이고 n² 은 100 입니다. n 이 100 일 때 두 값이 같아집니다. 그 뒤로는 100n 쪽이 계속 덜 듭니다.

아래 그림은 n 을 0 부터 200 까지 늘리며 두 비용을 그린 것입니다. 곧게 오르는 선이 100n 입니다. 휘어 오르는 선이 n² 입니다. 두 선은 n 이 100 일 때 만납니다. 그 뒤로 n² 이 위로 벌어집니다.

xychart-beta
    title "100n 과 n² 의 비용"
    x-axis "입력 크기 n" [0, 25, 50, 75, 100, 125, 150, 175, 200]
    y-axis "기본 연산 횟수" 0 --> 40000
    line [0, 2500, 5000, 7500, 10000, 12500, 15000, 17500, 20000]
    line [0, 625, 2500, 5625, 10000, 15625, 22500, 30625, 40000]

점근 분석이 말하는 「더 낫다」는 어느 크기를 넘어서면 순서가 다시는 뒤집히지 않는다는 뜻입니다. 그 크기가 얼마인지는 점근 분석이 알려 주지 않습니다.

상한과 하한을 적는 세 표기

줄인 결과는 기호로 적습니다. 가장 널리 쓰는 것이 빅오 표기법입니다. O(n²) 이라고 쓰고 「빅오 엔 제곱」이라고 읽습니다.

빅오의 뜻은 수학으로 정해져 있습니다. f(n) 을 센 비용 식이라고 합시다. g(n) 은 n² 처럼 비교할 꼴입니다.

f(n) = O(g(n)) 은 g(n) 에 알맞은 수를 곱한 선이 어느 크기부터 f(n) 보다 늘 위에 있다는 뜻입니다. f(n) 은 그 선을 넘지 않습니다. 이런 선을 f(n) 의 상한(upper bound)이라고 합니다.

기호로 적으면 값이 둘 나옵니다. c 는 g(n) 에 곱하는 양수입니다. n₀ 는 「이 크기부터」를 뜻하는 수입니다. 둘을 알맞게 골라 n₀ 이상인 모든 n 에서 f(n) ≤ c·g(n) 이 되면 f(n) = O(g(n)) 입니다.

앞 소절의 두 비용으로 확인해 보겠습니다. c 를 1, n₀ 를 100 으로 잡으면 100 이상인 모든 n 에서 100n ≤ n² 입니다. 그래서 100n = O(n²) 입니다. n₀ 가 곧 그래프에서 두 선이 만나던 곳입니다.

n₀ 가 이 정의에서 「점근」을 맡습니다. n₀ 보다 작은 n 에서는 무슨 일이 있든 따지지 않습니다. 어느 크기 너머에서만 성립하면 됩니다.

빅오는 상한만 말합니다. 그래서 상한을 헐겁게 잡아도 틀린 말은 아닙니다. n 번 도는 코드도 O(n²) 이고 O(2ⁿ) 입니다. 참이지만 쓸모는 적습니다.

이 헐거움을 메우려고 표기 둘을 더 씁니다. 빅오메가 표기법(Ω)은 하한(lower bound)을 말합니다. 하한은 어느 크기부터 f(n) 이 그 아래로 내려가지 않는 선입니다. 빅세타 표기법(Θ)은 상한과 하한을 함께 말합니다.

O 와 Ω 는 부등호 방향만 다릅니다. Θ 는 둘을 다 만족하는 것입니다.

이 표로 앞의 n² + n 을 따져 보겠습니다. n 이 1 이상이면 n² + n 은 n² 보다 크거나 같고 2n² 보다 작거나 같습니다. 상한과 하한을 모두 n² 꼴로 잡을 수 있으므로 n² + n = Θ(n²) 입니다. 비용의 꼴을 딱 맞게 말할 때 쓰는 것이 이 빅세타입니다.

경계와 경우의 차이

빅오를 최악, 빅오메가를 최선과 짝지어 외우는 일이 흔합니다. 둘은 서로 다른 질문에 답합니다.

경우는 어떤 입력을 두고 재느냐입니다. 일이 가장 많아지는 입력이 최악의 경우입니다. 가장 적어지는 입력이 최선의 경우입니다. 입력이 고르게 들어온다고 보고 평균을 낸 것은 평균의 경우입니다.

경계는 그렇게 정한 비용 식에 상한과 하한 중 무엇을 말하느냐입니다. 그래서 최악의 경우에도 세 표기를 다 쓸 수 있습니다. 최선의 경우에도 그렇습니다.

삽입 정렬로 두 축을 갈라 보겠습니다. 삽입 정렬은 원소를 하나씩 꺼냅니다. 그 원소를 앞쪽에 이미 정렬해 둔 부분의 알맞은 곳에 끼웁니다. 아래 표는 입력에 따라 비교 횟수가 어떤 꼴이 되는지 보입니다.

이미 정렬돼 있으면 원소마다 바로 앞 하나와만 비교하고 끝납니다. 거꾸로 정렬돼 있으면 원소마다 앞쪽을 끝까지 거슬러 갑니다.

그래서 「삽입 정렬은 O(n²) 이다」는 어떤 입력에서나 참입니다. 「삽입 정렬은 Θ(n²) 이다」는 모든 입력에서 참은 아닙니다. 정렬된 입력에서는 n 꼴로 끝나기 때문입니다.

자기 자신을 부르는 코드의 비용

자기 자신을 부르는 재귀 코드는 반복문처럼 횟수를 바로 셀 수 없습니다. 그래서 비용을 자기 자신으로 적은 식을 먼저 세웁니다. 이런 식을 재귀 관계식이라고 합니다.

병합 정렬이 대표적인 예입니다. 병합 정렬은 목록을 반으로 나눠 각각 정렬한 뒤, 정렬된 두 반쪽을 하나로 합칩니다. 합치는 일은 두 반쪽을 앞에서부터 한 번 훑으면 되므로 n 에 비례합니다.

크기 n 을 정렬하는 비용 T(n) 은 크기 n/2 를 정렬하는 비용 두 번에 합치는 비용 n 을 더한 것입니다. 식으로 적으면 T(n) = 2T(n/2) + n 입니다.

이 식을 풀려면 호출이 어떻게 갈라지는지 그려 보면 됩니다. 아래 그림에서 칸 하나는 호출 하나입니다. 칸 안의 수는 그 호출이 합치는 데 드는 일입니다.

flowchart TD
    subgraph D0["깊이 0 · 합 n"]
        A["n"]
    end
    subgraph D1["깊이 1 · 합 n"]
        B1["n/2"]
        B2["n/2"]
    end
    subgraph D2["깊이 2 · 합 n"]
        C1["n/4"]
        C2["n/4"]
        C3["n/4"]
        C4["n/4"]
    end
    A --> B1
    A --> B2
    B1 --> C1
    B1 --> C2
    B2 --> C3
    B2 --> C4
    D2 ~~~ R["크기가 1 이 될 때까지 같은 꼴"]

깊이가 하나 내려갈 때마다 호출은 두 배로 늡니다. 호출마다 맡은 크기는 절반이 됩니다. 그래서 어느 깊이에서나 합은 n 입니다. 크기가 1 이 될 때까지 반으로 나누는 횟수는 앞에서 본 log n 이므로 깊이도 log n 쯤 됩니다.

깊이마다 합이 n 입니다. 깊이는 log n 개입니다. 그래서 전체는 n log n 꼴입니다. 병합 정렬이 Θ(n log n) 인 이유가 이것입니다.

이런 꼴의 재귀 관계식을 한 번에 푸는 공식으로 마스터 정리가 있습니다.

메모리 비용과 한 번당 비용

이 소절은 점근 분석을 넓혀 쓰는 두 방법을 봅니다. 하나는 재는 대상을 시간에서 메모리로 바꿉니다. 다른 하나는 재는 대상은 시간 그대로 두고, 비용을 세는 단위를 연산 한 번에서 여러 번의 묶음으로 바꿉니다.

먼저 메모리입니다. 입력이 커질 때 코드가 쓰는 메모리가 어떤 꼴로 느는지를 점근 분석으로 본 것이 공간 복잡도입니다. 시간 복잡도와 같은 방법을 대상만 바꿔 쓴 것입니다.

다음은 세는 단위입니다. 같은 연산을 연달아 여러 번 했을 때 드는 비용을 모두 더합니다. 그 합을 횟수로 나눠 한 번당 비용을 말합니다. 이것을 분할 상환 비용이라고 합니다.

동적 배열에 값을 붙이는 연산이 이 방식으로 보는 예입니다. 칸이 모자라면 배열을 두 배로 키웁니다. 이때 원소를 전부 옮겨 담으므로 그 한 번은 n 꼴입니다.

대신 이 일은 드물게 일어납니다. n 번 붙이는 비용을 모두 더해도 n 꼴에 머뭅니다. 한 번당으로 나누면 상수 꼴입니다. 한 번씩만 보면 가장 비싼 한 번 때문에 붙이기가 n 꼴처럼 보였을 것입니다.

점근 분석이 가리는 비용

점근 분석은 버린 부분을 다시 보여 주지 않습니다. 그 부분이 결과를 뒤집는 상황에서는 답을 주지 못합니다.

첫째는 입력이 작을 때입니다. 앞의 100n 과 n² 처럼 n₀ 아래에서는 더 빨리 자라는 꼴이 오히려 덜 걸릴 수 있습니다. 병합 정렬을 짤 때 조각이 작아지면 삽입 정렬로 바꿔 정리하게 짜는 것도 이 때문입니다.

둘째는 메모리를 읽는 방식입니다. 점근 분석은 기본 연산 하나에 드는 시간이 모두 같다고 봅니다. 하지만 배열을 앞에서부터 차례로 읽는 코드는 연결 리스트를 노드마다 따라가는 코드보다 같은 횟수라도 덜 걸리는 경우가 많습니다. 가까운 메모리를 이어 읽을 때 시간이 줄어드는 이 성질이 캐시 지역성입니다.

점근 분석은 방법을 고르는 첫 기준으로 씁니다. 사용자 목록이나 로그처럼 계속 쌓이는 데이터를 다룬다면 꼴을 먼저 봅니다. 입력 크기가 늘 작게 정해져 있다면 꼴보다 잰 값이 더 믿을 만합니다.

시간을 직접 재는 방법은 따로 있습니다. 여러 방법을 같은 조건에서 재어 비교하는 일이 벤치마크입니다. 코드의 어느 부분이 시간을 먹는지 찾는 일은 프로파일링입니다.

관련 항목

점근 분석의 결과를 적는 표기법

점근 표기법 · 빅오 표기법 · 빅오메가 표기법 · 빅세타 표기법 · 리틀오 표기법 · 리틀오메가 표기법

점근 분석으로 재는 비용 지표

시간 복잡도 · 공간 복잡도 · 분할 상환 비용 · 보조 공간

점근 분석이 기준으로 삼는 입력의 경우

최악의 경우 · 평균의 경우 · 최선의 경우 · 입력 크기

재귀 알고리즘의 비용을 푸는 도구

재귀 관계식 · 재귀 트리 · 마스터 정리 · 분할 정복 · 재귀

점근 분석으로 비교하는 알고리즘과 자료구조

알고리즘 · 정렬 · 삽입 정렬 · 병합 정렬 · 이진 탐색 · 동적 배열 · 자료구조

점근 분석이 못 보는 비용을 재는 수단

벤치마크 · 프로파일링 · 캐시 지역성 · 성능 분석

이것이 속하는 상위 분류

알고리즘 분석 · 계산 복잡도 이론 · 복잡도 클래스

점근 분석을 떠받치는 수학 개념

극한 · 점근선 · 로그 함수 · 다항식 · 지수 함수