빅세타 표기법

빅세타 표기법은 데이터가 늘 때 코드가 할 일이 불어나는 모양을 딱 맞게 적어 줍니다. 그 모양보다 빨리 불어나지도 않고 느리게 불어나지도 않는다는 뜻입니다. 위쪽만 막아 두는 빅오 표기법보다 한 걸음 더 좁혀 말하는 약속입니다.

상세

택배 도착 날짜를 묻는다고 해 봅시다. 「한 달 안에 옵니다」는 틀린 말이 아닙니다. 그런데 이틀 만에 오는 택배에도 맞는 말이라 언제 받을지 가늠이 안 됩니다. 「이틀에서 사흘 사이에 옵니다」라고 해야 날짜가 잡힙니다.

빅세타 표기법은 코드의 비용에 대해 이 「사이」를 적는 약속입니다. n 은 코드가 다루는 데이터의 개수입니다. Θ(n) 은 데이터가 늘 때 일이 n 과 같은 모양으로 는다는 뜻입니다. 위로는 n 의 몇 배를 넘지 않습니다. 아래로는 n 의 몇 배 밑으로 내려가지 않습니다.

Θ 는 그리스 문자 세타의 대문자입니다. Θ(n) 은 「세타 엔」이라고 읽습니다. 알고리즘의 비용을 딱 맞게 말하고 싶을 때 쓰는 표기입니다.

같은 일을 하는 표기로 빅오 표기법이 더 널리 알려져 있습니다. 빅오는 비용이 자라는 모양의 위쪽만 막아 둡니다. 빅세타는 거기에 아래쪽까지 막아 모양을 하나로 못박습니다.

입력 크기와 단계 수

빅세타가 적는 대상은 단계 수입니다. 비교 한 번, 더하기 한 번 같은 기본 동작이 몇 번 일어나는지를 셉니다. 초로 재면 기계와 언어에 따라 값이 바뀝니다. 단계 수는 무엇을 한 단계로 칠지만 정하면 코드만 보고 정해집니다.

아래는 배열의 합을 구하는 자바 코드입니다. 줄마다 몇 번 실행되는지 오른쪽 주석에 적었습니다. 반복문 줄은 따로 세지 않았습니다.

int sum(int[] a) {
  int s = 0;       // 1번
  for (int x : a)
    s += x;        // n번
  return s;        // 1번
}

다 더하면 n + 2 번입니다. 배열이 어떤 값을 담고 있든 이 수는 바뀌지 않습니다. 이 n + 2 가 어떤 모양으로 자라는지를 다음 소절에서 따집니다.

위에서 덮는 선과 아래에서 받치는 선

이 소절은 빅세타를 세우는 두 한계를 선으로 그려 봅니다. n 을 가로축에, 단계 수를 세로축에 놓으면 비용은 선 하나가 됩니다. 이 선보다 늘 위에 있는 선이 상한입니다. 늘 아래에 있는 선이 하한입니다.

식으로 적으려면 이름 둘이 필요합니다. f(n) 은 앞에서 세어 낸 단계 수입니다. 배열의 합이라면 n + 2 입니다. g(n) 은 f(n) 과 비교할 모양입니다. n 이나 n² 처럼 곱해진 수가 없는 단순한 식을 씁니다.

모양과 선은 다릅니다. 모양 g(n) 에 양수 c 를 곱하면 선 c·g(n) 이 됩니다. 같은 n 모양이라도 c 가 1 이면 n, c 가 2 이면 2n 이라는 다른 선입니다.

n 이 작을 때는 선의 위아래가 뒤집히기도 합니다. n + 2 와 2n 을 보면 n 이 1 일 때 3 과 2 라서 2n 이 아래에 있습니다. 그래서 n 이 작을 때는 무시하고 어느 크기부터만 봅니다. 그 크기를 문턱이라고 합니다.

빅오는 상한을 적는 표기입니다. f(n) = O(g(n)) 은 n 이 문턱을 넘은 뒤로 f(n) 이 선 c·g(n) 을 넘지 않는다는 뜻입니다.

빅오메가 표기법은 하한을 적는 표기입니다. Ω(g(n)) 으로 적습니다. n 이 문턱을 넘은 뒤로 f(n) 이 c·g(n) 밑으로 내려가지 않는다는 뜻입니다.

빅세타는 이 둘을 같은 g(n) 으로 한꺼번에 세웁니다. 같은 모양이 위에서 덮고 아래에서도 받치면 f(n) = Θ(g(n)) 입니다. 아래 표는 세 표기를 나란히 놓은 것입니다.

마지막 줄에는 곱하는 수가 둘입니다. 아래 선에 곱하는 c₁ 과 위 선에 곱하는 c₂ 가 서로 달라도 됩니다. 모양 g(n) 만 같으면 됩니다.

두 선 사이에 끼운 비용

앞의 n + 2 로 해 봅니다. 아래에서는 n 이 받칩니다. n + 2 는 언제나 n 보다 2 가 크기 때문입니다. 위에서는 2n 이 덮습니다. n 이 2 이상이면 n + 2 ≤ 2n 이 성립합니다.

받치는 선과 덮는 선이 모두 n 의 모양입니다. 그래서 n + 2 = Θ(n) 입니다. 이때 c₁ 은 1, c₂ 는 2, 문턱은 2 입니다.

이중 반복문으로 배열의 모든 쌍을 한 번씩 비교하면 비교가 n(n-1)/2 번 일어납니다. n 이 4 이면 4 × 3 / 2 로 6 번입니다. 이 수가 n² 모양에 끼이는지 봅니다.

위에서는 n²/2 가 덮습니다. n(n-1)/2 는 n²/2 에서 n/2 를 뺀 값이기 때문입니다. 아래에서는 n²/4 가 받칩니다. n 이 2 이상이면 n(n-1)/2 ≥ n²/4 가 성립합니다. 아래 그림에 세 선을 그렸습니다.

xychart-beta
    title "n(n-1)/2 를 끼운 두 선"
    x-axis "n" [2, 4, 6, 8, 10]
    y-axis "비교 횟수" 0 --> 50
    line [2, 8, 18, 32, 50]
    line [1, 6, 15, 28, 45]
    line [1, 4, 9, 16, 25]

맨 위 선이 n²/2, 가운데 선이 n(n-1)/2, 맨 아래 선이 n²/4 입니다. n 이 2 일 때 가운데 선이 아래 선과 만납니다. 그 뒤로 가운데 선은 늘 두 선 사이에 있습니다.

두 선이 모두 n² 모양이므로 n(n-1)/2 = Θ(n²) 입니다. 곱하는 수 1/2 와 1/4 은 모양을 바꾸지 않습니다. 그래서 이 수는 c₁ 과 c₂ 에 들어갑니다. 표기에는 나타나지 않습니다.

작은 항과 곱해진 수가 사라지는 까닭

3n² + 5n + 7 같은 식도 Θ(n²) 으로 적습니다. n 이 커지면 가장 빨리 불어나는 항 하나가 전체 크기를 정합니다. 5n 과 7 은 n 이 커질수록 3n² 옆에서 작아져서 모양을 바꾸지 못합니다.

곱해진 3 은 무엇을 한 단계로 칠지에 따라 바뀝니다. 더하기와 대입을 따로 세면 이 수가 커집니다. 둘을 묶어 한 단계로 세면 작아집니다.

단계 수를 실제 시간으로 옮길 때도 이 수가 흔들립니다. 단계 하나의 무게가 기계와 언어마다 다르기 때문입니다. 그래서 빅세타는 모양만 비교하려고 이 수를 c₁ 과 c₂ 안에 넣습니다.

n 이 한없이 커질 때의 모양만 보는 이런 분석을 점근 분석이라고 합니다. 빅오와 빅오메가와 빅세타는 모두 점근 분석이 쓰는 표기입니다.

빅오와 빅세타가 갈리는 대목

빅오는 위에서 덮기만 하면 맞는 말입니다. 그래서 n + 2 는 O(n) 입니다. O(n²) 도 맞고 O(2ⁿ) 도 맞습니다. 뒤의 둘은 비용을 부풀려 말할 뿐입니다.

빅세타는 이렇게 부풀릴 수 없습니다. n + 2 를 Θ(n²) 이라고 적으면 틀립니다. 곱하는 수를 아무리 작은 양수로 잡아도 n 이 커지면 c·n² 이 n + 2 를 넘어서기 때문입니다. 아래에서 받치는 선이 못 됩니다.

1 모양은 n 이 아무리 커져도 일이 늘지 않는 모양입니다. 데이터 개수와 상관없이 늘 같은 수의 단계만 도는 코드가 그렇습니다. 아래 표는 n + 2 에 1·n·n² 세 모양을 대 본 결과입니다.

빅오로 맞는 모양은 여럿입니다. 빅세타로 맞는 모양은 n 하나뿐입니다. 빅세타가 비용을 하나로 못박는다는 말이 이 뜻입니다.

이 차이는 두 코드를 비교할 때 드러납니다. 코드 A 가 O(n²) 이고 코드 B 가 O(n) 이라고 해 봅시다. 빅오만으로는 A 가 일을 더 한다고 말할 수 없습니다. A 도 n 만큼만 일할 수 있기 때문입니다. A 가 Θ(n²) 이라고 밝혀져야 데이터가 커질 때 A 가 일을 더 한다고 말할 수 있습니다.

실무에서는 「O(n) 이다」라고 흔히 말합니다. 그런데 뜻은 빅세타인 경우가 많습니다. 덮는 선 가운데 가장 낮은 선을 골라 말하면 그 선이 대개 아래에서도 받치기 때문입니다. 교재와 논문은 둘을 가려 씁니다.

입력에 따라 갈리는 비용

배열의 합은 어떤 배열을 넣어도 n + 2 단계였습니다. 그런데 입력의 내용에 따라 단계 수가 바뀌는 코드도 있습니다. 순차 탐색이 그렇습니다.

순차 탐색은 앞에서부터 하나씩 비교하며 값을 찾는 방법입니다. 찾는 값이 맨 앞에 있으면 비교 1번에 끝납니다. 맨 뒤에 있거나 아예 없으면 n 번 비교합니다.

이런 코드는 비용을 경우별로 나눠 적습니다. 가장 빨리 끝나는 입력의 비용이 최선의 경우입니다. 가장 오래 걸리는 입력의 비용이 최악의 경우입니다. 아래 표는 순차 탐색에 붙일 수 있는 말과 그 말이 맞는지를 모은 것입니다.

마지막 줄이 빅세타를 쓸 때 가장 자주 틀리는 곳입니다. 경우를 밝히지 않은 Θ 는 모든 입력에서 그 모양이라는 주장입니다. 1번에 끝나는 입력이 하나라도 있으면 아래 선 n 이 받치지 못합니다.

그래서 입력에 따라 비용이 갈리는 코드는 「최악의 경우 Θ(n)」처럼 경우를 붙여 적습니다. 배열의 합처럼 늘 같은 단계를 도는 코드는 경우를 붙이지 않고 Θ(n) 이라고만 적어도 됩니다.

메모리에도 쓰는 표기

빅세타는 시간만 적는 표기가 아닙니다. 입력이 이미 차지한 것 말고 코드가 메모리를 얼마나 더 쓰는지도 같은 방식으로 적습니다. 시간 쪽을 시간 복잡도, 메모리 쪽을 공간 복잡도라고 합니다.

배열을 뒤집는 두 방법이 예입니다. 새 배열을 하나 만들어 거꾸로 옮겨 담으면 n 칸을 더 씁니다. 그래서 추가 메모리가 Θ(n) 입니다. 두 끝의 값을 맞바꾸며 가운데로 좁혀 가면 변수 몇 개만 더 씁니다. 이쪽은 Θ(1) 입니다.

빅세타가 알려 주지 않는 비용

빅세타도 곱해진 수와 작은 항을 버립니다. 그래서 같은 Θ(n) 인 두 코드라도 한 단계의 무게가 다르면 걸리는 시간이 크게 갈립니다. 메모리에서 값 하나를 읽는 것과 데이터베이스에 쿼리를 한 번 보내는 것이 똑같이 한 단계로 셈해집니다.

n 이 작을 때도 모양보다 버린 수가 전체를 좌우합니다. 모양이 딱 맞게 적혀 있어도 지금 몇 초 걸리는지는 프로파일링이나 벤치마크로 재 봐야 압니다. 빅세타가 알려 주는 것은 데이터가 커질 때 비용이 어떤 모양으로 느는지입니다.

관련 항목

빅세타 표기법과 짝을 이루는 점근 표기

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

빅세타 표기법이 위아래로 묶는 한계

상한 · 하한 · 점근 분석 · 증가 속도

빅세타 표기법으로 적는 비용

시간 복잡도 · 공간 복잡도 · 최악의 경우 분석 · 최선의 경우 분석 · 평균적 경우 분석 · 분할 상환 분석

빅세타 표기법이 이름 붙이는 증가 모양

상수 시간 · 로그 시간 · 선형 시간 · 선형 로그 시간 · 이차 시간 · 다항 시간 · 지수 시간

빅세타 표기법으로 비용을 적는 알고리즘

알고리즘 · 순차 탐색 · 이진 탐색 · 삽입 정렬 · 병합 정렬 · 정렬

빅세타 표기법이 한 단계로 뭉뚱그리는 비용

왕복 시간 · 데이터베이스 · 디스크 입출력 · 캐시 미스 · N+1 문제

빅세타 표기법 밖에서 시간을 재는 수단

프로파일링 · 벤치마크 · 부하 테스트 · 성능

빅세타 표기법이 빌려 온 수학 개념

함수 · 부등식 · 극한 · 다항식