빅오메가 표기법

빅오메가 표기법은 데이터가 늘어날 때 코드가 할 일이 적어도 얼마나 불어나는지를 짧은 식 하나로 적어 줍니다. 빅오 표기법은 넘지 않는 천장을 적습니다. 빅오메가는 내려가지 않는 바닥을 적습니다.

상세

책 한 권에서 오타를 전부 찾는다고 해 봅시다. 아무리 눈이 밝은 사람도 모든 쪽을 한 번은 넘겨야 합니다. 책이 두 배로 두꺼워지면 넘길 쪽도 적어도 두 배가 됩니다.

빅오메가 표기법은 이 「적어도」를 코드에 대해 적는 약속입니다. n 은 코드가 다루는 데이터의 개수입니다. Ω(n) 이라고 적으면 데이터가 늘어난 만큼 일도 적어도 그만큼은 늘어난다는 뜻입니다.

Ω 는 그리스 문자 오메가의 대문자입니다. Ω(n) 은 「빅오메가 엔」이라고 읽습니다.

이 표기는 빅오 표기법과 짝을 이룹니다. 빅오는 「이보다 더 불어나지 않는다」는 천장을 적습니다. 빅오메가는 「이보다 덜 불어나지 않는다」는 바닥을 적습니다.

천장만으로는 답이 안 나오는 질문이 있습니다. 「이 코드를 더 줄일 수 있나」가 그렇습니다. 천장은 지금 코드가 얼마나 오래 걸릴 수 있는지만 알려 줍니다. 더 줄일 여지가 있는지는 바닥을 알아야 답할 수 있습니다.

초 대신 세는 동작 수

빅오메가는 시간을 초로 재지 않습니다. 비교 한 번, 더하기 한 번 같은 기본 동작이 몇 번 일어나는지를 셉니다. 초는 기계와 언어에 따라 바뀝니다. 동작 수는 코드만 보면 정해집니다.

메모리도 같은 방식으로 셉니다. 동작 수를 세면 시간 복잡도의 바닥이 됩니다. 코드가 더 쓰는 메모리 칸 수를 세면 공간 복잡도의 바닥이 됩니다.

아래에서 받치는 선

이 소절은 「Ω(n²) 이다」라는 말이 수학으로는 무슨 뜻인지 코드 하나로 봅니다. 아래는 배열에 같은 값이 두 번 나오는지 보는 자바 코드입니다. 같은 값이 하나도 없는 배열을 넣었을 때 비교가 몇 번 도는지 오른쪽 주석에 적었습니다.

boolean hasDup(int[] a) {
  int n = a.length;
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
      if (a[i] == a[j])   // n(n-1)/2번
        return true;
  return false;
}

바깥 반복이 원소 하나를 고르면 안쪽 반복이 그 뒤의 원소와 전부 비교합니다. 그래서 모든 쌍을 한 번씩 봅니다. 쌍의 수는 n(n−1)/2 입니다.

이 비교 횟수를 f(n) 이라고 둡니다. 받쳐 줄 식 n² 은 g(n) 이라고 둡니다. 빅오메가의 정의는 이렇게 함수 둘을 비교하는 꼴입니다.

g(n) 에는 n 이 커질 때 식이 자라는 꼴만 남깁니다. 이 꼴을 증가 차수라고 하고, 아래에서는 쉽게 모양이라고 부릅니다. 3n² 과 n² 은 모양이 같습니다.

첫째로 g(n) 에 곱할 양수 c 가 필요합니다. n² 은 n(n−1)/2 보다 늘 큽니다. 받치는 선은 아래에 있어야 하므로 n² 을 그대로 두면 안 됩니다. c 를 1/4 로 낮춰 n²/4 와 비교합니다.

둘째로 「이 n 부터 따진다」는 문턱 n₀ 이 필요합니다. n 이 1 이면 비교 횟수는 0 입니다. 이 0 은 받치는 선 n²/4 = 0.25 보다 아래입니다. 선이 비교 횟수를 받쳐 주지 못하는 것입니다.

n₀ 을 2 로 잡으면 이 문제가 사라집니다. 부등식 n(n−1)/2 ≥ n²/4 는 양쪽에 4 를 곱해 정리하면 n ≥ 2 와 같은 식이 됩니다. 아래 그림에 두 선을 그렸습니다.

xychart-beta
    title "n(n-1)/2 와 받치는 선 n²/4"
    x-axis "n" [1, 2, 3, 4]
    y-axis "비교 횟수" 0 --> 6
    line [0, 1, 3, 6]
    line [0.25, 1, 2.25, 4]

n 이 커질수록 더 가파르게 오르는 선이 비교 횟수 n(n−1)/2 입니다. 완만한 선이 받치는 선 n²/4 입니다.

n 이 1 일 때는 비교 횟수가 n²/4 아래로 내려갑니다. n 이 2 일 때 두 선이 1 에서 만납니다. 그 뒤로는 비교 횟수가 늘 n²/4 위에 있습니다. 문턱 n₀ 은 이렇게 작은 n 에서 잠깐 내려가는 것을 봐줍니다.

정리하면 f(n) = Ω(g(n)) 은 이런 c 와 n₀ 을 찾을 수 있다는 뜻입니다. n₀ 이상인 모든 n 에서 f(n) ≥ c·g(n) 이 성립하면 됩니다. 그래서 n(n−1)/2 = Ω(n²) 입니다.

이렇게 아래에서 받치는 선을 하한이라고 부릅니다. 빅오메가는 하한을 적는 표기입니다.

Ω(n²) 은 함수 하나가 아니라 함수들의 집합입니다. c·n² 꼴의 선이 아래에서 받쳐 주는 함수를 모두 모은 것입니다. n(n−1)/2 는 그 집합에 드는 함수 하나입니다.

f(n) = Ω(g(n)) 의 등호는 양쪽이 같다는 뜻이 아닙니다. 왼쪽 함수가 오른쪽 집합에 든다는 뜻입니다. 「속한다」를 뜻하는 기호를 써서 f(n) ∈ Ω(g(n)) 으로 적는 교재도 있습니다.

낮게 잡아도 틀리지 않는 바닥

하한은 낮게 잡을수록 성립하기 쉽습니다. n(n−1)/2 는 Ω(n²) 입니다. 동시에 Ω(n) 이기도 합니다. n 이 커지면 n(n−1)/2 가 n 보다 훨씬 빨리 자라기 때문입니다.

더 내려가면 Ω(1) 도 참입니다. Ω(1) 은 「적어도 일정한 양은 한다」는 뜻이라 거의 모든 코드에 맞습니다. 참이지만 아무것도 알려 주지 않습니다.

쓸모 있는 바닥을 말하려면 받칠 수 있는 선 가운데 가장 높은 것을 고릅니다. 앞의 코드라면 Ω(n²) 입니다.

빅오와 뒤집힌 관계

빅오는 n₀ 이상인 모든 n 에서 f(n) ≤ c·g(n) 이 되는 c 와 n₀ 이 있다는 뜻입니다. 빅오메가의 f(n) ≥ c·g(n) 과 견주면 부등호 방향만 다릅니다.

그래서 한쪽을 뒤집으면 다른 쪽이 됩니다. f(n) = Ω(g(n)) 이면 g(n) = O(f(n)) 입니다. 거꾸로도 성립합니다.

n² 과 n 으로 보면 이렇습니다. n² 은 n 에 받쳐지므로 n² = Ω(n) 입니다. 같은 관계를 n 쪽에서 보면 n 이 n² 에 덮이므로 n = O(n²) 입니다.

같은 모양이 천장과 바닥을 함께 맡을 때도 있습니다. 앞의 비교 횟수 n(n−1)/2 는 모든 n 에서 n² 이하이므로 O(n²) 입니다. 앞 소절에서 Ω(n²) 인 것도 봤습니다.

위아래를 같은 모양으로 묶는 이 경우를 빅세타 표기법으로 Θ(n²) 이라고 적습니다. 세 표기를 표로 모으면 이렇습니다.

경우와 바닥은 다른 축

이 소절은 삽입 정렬 하나로 두 가지를 가릅니다. 경우(어떤 입력을 두고 재나)와 바닥(그 비용을 아래에서 받치는 선)입니다. 빅오메가를 「일이 가장 적은 입력의 비용」으로 외우는 일이 흔합니다. 하지만 경우와 바닥은 서로 다른 질문에 답합니다.

경우는 어떤 입력을 두고 재느냐입니다. 일이 가장 적어지는 입력이 최선의 경우입니다. 일이 가장 많아지는 입력이 최악의 경우입니다.

바닥은 그렇게 고른 경우의 비용을 아래에서 받치는 선입니다. 그래서 최악의 경우에도 빅오메가를 쓸 수 있습니다.

삽입 정렬은 원소를 하나씩 꺼내 앞쪽에 이미 정렬해 둔 부분의 알맞은 위치에 끼웁니다. 이미 정렬된 목록이 들어오면 원소마다 바로 앞 하나와만 비교하고 끝납니다. 거꾸로 정렬된 목록이 들어오면 원소마다 앞쪽을 끝까지 거슬러 가며 비교합니다.

아래 표는 삽입 정렬을 두고 흔히 하는 말 셋이 참인지 가른 것입니다.

첫 줄과 셋째 줄은 경우를 밝히지 않았습니다. 경우를 밝히지 않은 빅오메가는 모든 입력에서 성립해야 합니다. 그래서 일이 가장 적은 입력까지 받쳐야 합니다. 결국 최선의 경우의 바닥과 같아집니다.

「빅오메가는 최선의 경우」라고 외우는 까닭이 여기 있습니다. 둘째 줄처럼 최악의 경우를 밝히고 쓰면 이 말은 맞지 않습니다.

코드 하나의 바닥과 문제의 바닥

지금까지 본 바닥은 코드 하나의 바닥입니다. 빅오메가가 더 큰 힘을 쓰는 것은 문제 자체의 바닥을 말할 때입니다. 문제의 바닥은 그 문제를 푸는 어떤 코드도 그보다 덜 일할 수 없다는 선입니다.

정렬되지 않은 배열에서 가장 큰 값을 찾는 문제가 쉬운 예입니다. 원소를 하나라도 안 보고 답을 내면 그 안 본 원소가 가장 큰 값일 수 있습니다. 그래서 어떤 코드든 원소를 전부 한 번씩은 봐야 합니다.

따라서 이 문제는 Ω(n) 입니다. 앞에서부터 한 번 훑는 코드는 O(n) 이므로 이 바닥에 닿아 있습니다. 이 문제를 두고는 모양이 더 나은 코드를 찾을 필요가 없습니다.

비교 정렬의 바닥

두 값을 비교해서 순서를 정하는 방식으로만 정렬하는 것을 비교 정렬이라고 합니다. 삽입 정렬과 병합 정렬이 비교 정렬입니다. 비교 정렬에는 어떤 방법을 써도 넘을 수 없는 바닥이 있습니다.

원소가 a, b, c 셋일 때로 봅니다. 셋을 줄 세우는 순서는 여섯 가지입니다. 비교 한 번은 「예」와 「아니오」 두 갈래로 나뉩니다. 아래 그림은 비교를 거듭하며 여섯 순서를 가르는 한 방법입니다.

flowchart TD
    Q1{"a 가 b 보다 작나"}
    Q1 -->|예| Q2{"b 가 c 보다 작나"}
    Q1 -->|아니오| Q3{"a 가 c 보다 작나"}
    Q2 -->|예| L1["a · b · c"]
    Q2 -->|아니오| Q4{"a 가 c 보다 작나"}
    Q4 -->|예| L2["a · c · b"]
    Q4 -->|아니오| L3["c · a · b"]
    Q3 -->|예| L4["b · a · c"]
    Q3 -->|아니오| Q5{"b 가 c 보다 작나"}
    Q5 -->|예| L5["b · c · a"]
    Q5 -->|아니오| L6["c · b · a"]

맨 아래 끝에 여섯 순서가 하나씩 매달려 있습니다. 위에서 끝까지 내려가며 거친 마름모 수가 그 순서를 알아내는 데 쓴 비교 횟수입니다. 가장 긴 길은 비교가 세 번입니다.

두 번으로 줄일 수는 없습니다. 비교 두 번이 만드는 갈래는 2 × 2 로 넷뿐입니다. 넷으로는 여섯 순서를 다 가르지 못합니다. 그래서 셋을 비교로 정렬하는 방법은 무엇이든 적어도 한 입력에서는 세 번 비교합니다.

원소가 n 개면 순서의 가짓수는 n! 입니다. n! 은 1 부터 n 까지 곱한 값이고 「n 팩토리얼」이라고 읽습니다. 셋이면 1 × 2 × 3 = 6 으로 앞의 여섯 순서와 맞습니다.

비교 k 번이 만드는 갈래는 2 를 k 번 곱한 2ᵏ 개까지입니다. 갈래 하나가 순서 하나를 맡아야 하므로 2ᵏ 이 n! 이상이 될 만큼 비교해야 합니다.

열 개로 계산해 봅니다. 10! 은 3,628,800 입니다. 2²¹ 은 2,097,152 입니다. 2²² 는 4,194,304 입니다. 그래서 열 개를 비교로 정렬하는 방법은 무엇이든 적어도 한 입력에서는 22 번 이상 비교합니다.

이 비교 횟수를 식으로 적으려면 로그가 필요합니다. log₂(n!) 은 2 를 몇 번 곱해야 n! 이 되는지를 센 값입니다. 2ᵏ 이 n! 이상이라는 조건은 k 가 log₂(n!) 이상이라는 말과 같습니다.

n 이 커지면 log₂(n!) 은 n log n 과 같은 모양으로 자랍니다. 까닭은 곱셈을 반만 봐도 드러납니다. n! 을 이루는 곱 가운데 큰 쪽 절반은 전부 n/2 이상입니다. 따라서 n! 은 n/2 를 n/2 번 곱한 값 이상입니다.

여기에 로그를 씌우면 log₂(n!) 은 (n/2)·log₂(n/2) 이상입니다. 앞에 곱해진 1/2 과 로그 안의 /2 는 모양을 바꾸지 않습니다. 그래서 이 바닥은 n log n 의 모양입니다.

그래서 비교 정렬은 최악의 경우 Ω(n log n) 입니다. 병합 정렬은 최악의 경우에도 O(n log n) 이므로 이 바닥에 닿아 있습니다. 비교만으로 정렬하는 방법을 아무리 궁리해도 병합 정렬보다 모양이 나은 것은 나오지 않습니다.

이 바닥은 비교로 순서를 가를 때의 이야기입니다. 값이 작은 정수라면 계수 정렬처럼 비교 없이 값을 칸 번호로 써서 정렬할 수 있습니다. 그런 방법은 이 바닥에 묶이지 않습니다.

바닥을 알 때 달라지는 판단

바닥을 알면 멈출 때를 압니다. 코드의 천장이 문제의 바닥과 같은 모양이면 그 코드는 모양으로는 더 줄일 수 없습니다. 그다음은 곱해진 수를 줄이는 일입니다. 그 일은 프로파일링으로 재 보면서 합니다.

바닥을 넘고 싶으면 문제의 조건을 바꿔야 합니다. 정렬되지 않은 배열에서 값 하나를 찾는 문제는 Ω(n) 입니다. 가장 큰 값 찾기와 같은 까닭으로 원소를 전부 봐야 하기 때문입니다.

배열을 미리 정렬해 두면 문제가 달라집니다. 이진 탐색으로 절반씩 버리며 찾을 수 있어 O(log n) 이 됩니다. 대신 정렬해 두는 비용과 정렬을 지키는 비용을 따로 냅니다. 데이터베이스가 인덱스를 두어 전부 훑지 않고 찾는 것도 같은 방식입니다.

관련 항목

빅오메가 표기법과 짝을 이루는 점근 표기

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

빅오메가 표기법이 나타내는 경계

하한 · 상한 · 점근적 최적 · 최적 알고리즘

빅오메가 표기법이 바닥을 적는 비용

시간 복잡도 · 공간 복잡도 · 최선의 경우 · 최악의 경우 · 평균의 경우

문제의 하한을 세우는 증명 기법

결정 트리 모델 · 적대자 논증 · 정보 이론적 하한 · 귀류법

빅오메가 표기법으로 바닥을 따지는 알고리즘

비교 정렬 · 삽입 정렬 · 병합 정렬 · 힙 정렬 · 순차 탐색 · 이진 탐색 · 정렬

비교 정렬의 하한에 묶이지 않는 정렬

계수 정렬 · 기수 정렬 · 버킷 정렬

빅오메가 표기법이 빌려 온 수학 개념

함수 · 팩토리얼 · 로그 함수 · 부등식 · 극한