빅오 표기법

빅오 표기법은 데이터가 늘어날 때 코드가 할 일이 얼마나 불어나는지를 짧은 식 하나로 적어 줍니다. 몇 초 걸렸는지는 적지 않고 불어나는 모양만 남깁니다. 그래서 기계와 언어가 달라도 두 코드를 같은 잣대로 비교할 수 있습니다.

상세

출석부에서 학생 한 명을 찾는 두 방법을 떠올려 봅시다. 이름만 알면 첫 줄부터 한 줄씩 읽어 내려갑니다. 학생이 두 배면 읽는 줄도 두 배가 됩니다.

출석 번호를 알면 그 번호 줄을 바로 짚습니다. 반이 커져도 한 번 짚으면 끝납니다. 두 방법은 오늘 몇 줄 읽었나보다 반이 커질 때 몇 줄을 읽게 되나에서 갈립니다.

빅오 표기법은 이 「커지면 몇 번이 되나」를 코드에 대해 적는 약속입니다. n 은 코드가 다루는 데이터의 개수입니다. 이름으로 훑는 방법은 O(n) 이라고 적습니다. 데이터가 늘어난 만큼 일도 늘어난다는 뜻입니다.

번호로 바로 짚는 방법은 O(1) 이라고 적습니다. 데이터가 늘어도 일이 늘지 않는다는 뜻입니다. O(n) 은 「오 엔」, O(1) 은 「오 일」이라고 읽습니다. 알고리즘과 자료구조의 비용을 말할 때 가장 자주 만나는 표기입니다.

이 약속이 없으면 비용을 「내 노트북에서 몇 초」로 말하게 됩니다. 그 숫자는 기계가 바뀌면 바뀝니다. 데이터가 늘면 어떻게 될지도 알려 주지 않습니다. 테스트 데이터 백 건에서 멀쩡하던 코드가 운영 데이터 백만 건에서 멈추는 일이 그래서 생깁니다.

입력 크기 n

앞에서 n 을 데이터의 개수라고 했습니다. 무엇을 하나로 세는지는 데이터마다 다릅니다. 배열이면 원소 개수, 문자열이면 글자 수, 테이블이면 행 수입니다.

무엇을 n 으로 둘지는 쓰는 사람이 정합니다. 그래서 「n 은 주문 건수」처럼 먼저 밝혀 둡니다.

크기를 재는 기준이 둘인 입력은 변수도 둘을 씁니다. 사용자 n 명이 저마다 주문 m 건을 가지고 있다고 해 봅시다. 그 주문을 전부 훑는 코드는 O(n × m) 이라고 적습니다.

초 대신 세는 단계 수

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

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

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

다 더하면 n + 2 번입니다. 배열이 열 칸이면 열두 번입니다. 백만 칸이면 백만두 번입니다.

빅오로는 O(n) 이라고 적습니다. 뒤의 2 가 사라지는 까닭은 다음 소절이 다룹니다.

작은 항과 곱해진 수를 지우는 까닭

3n² + 5n + 7 이라는 식 하나로 빅오가 왜 한 항만 남기는지 보입니다. 이중 반복문 앞뒤로 준비 작업이 붙은 코드를 세면 이런 식이 나옵니다. 빅오는 이 식을 O(n²) 으로 줄여 적습니다.

n 을 키워 보면 까닭이 보입니다. 아래 표는 식의 세 항을 n 마다 따로 계산한 것입니다.

n 이 1,000 이기만 해도 5n 과 7 을 합한 값은 3n² 의 오백분의 일에 못 미칩니다. n 이 커질수록 전체 크기는 가장 크게 불어나는 항 하나가 정합니다. n 이 한없이 커질 때의 모양만 보는 이런 분석이 점근 분석입니다.

곱해진 3 을 지우는 까닭은 따로 있습니다. 같은 코드도 기계와 언어에 따라 한 단계에 드는 시간이 다릅니다. 그 차이는 결국 곱해진 수에 섞여 들어갑니다. 모양만 비교하려고 그 수를 지웁니다.

위에서 덮는 선

이 소절은 「O(n) 이다」라는 말이 수학으로는 무슨 뜻인지 봅니다. 이 표기는 수학에서 함수 둘이 커지는 빠르기를 비교할 때 쓰던 것을 컴퓨터 과학이 가져왔습니다. 그래서 정의도 함수 둘을 비교하는 꼴입니다.

앞의 n + 2 를 n 과 비교해 봅니다. 단계 수 n + 2 를 f(n) 이라고 둡니다. 비교할 모양 n 은 g(n) 이라고 둡니다.

첫째로 g(n) 에 곱할 양수 c 가 필요합니다. n 은 n + 2 보다 늘 2 가 작습니다. 그래서 n 을 그대로 두면 n + 2 를 위에서 덮지 못합니다. c 를 2 로 잡아 2n 과 비교합니다.

둘째로 「이 n 부터 따진다」는 문턱 n₀ 이 필요합니다. 2n 도 처음부터 덮지는 못하기 때문입니다. n 이 1 일 때 2n 은 2 라서 n + 2 인 3 보다 작습니다.

n₀ 을 2 로 잡으면 이 문제가 사라집니다. n 이 2 이상이면 늘 n + 2 ≤ 2n 입니다. 아래 그림에 세 선을 그렸습니다.

xychart-beta
    title "n + 2 를 덮는 선"
    x-axis "n" [1, 2, 3, 4, 5, 6]
    y-axis "단계 수" 0 --> 12
    line [2, 4, 6, 8, 10, 12]
    line [3, 4, 5, 6, 7, 8]
    line [1, 2, 3, 4, 5, 6]

가장 가파르게 오르는 선이 2n 입니다. 기울기가 같은 나머지 두 선 가운데 위쪽이 n + 2, 아래쪽이 n 입니다.

n 이 1 일 때는 n + 2 가 2n 위로 삐져나옵니다. n 이 2 일 때 두 선이 만납니다. 그 뒤로는 2n 이 늘 위에 있습니다. 문턱 n₀ 은 이렇게 작은 n 에서 잠깐 삐져나오는 것을 봐줍니다.

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

이렇게 위에서 덮는 선을 상한이라고 부릅니다. 빅오는 상한을 적는 표기입니다. 그래서 n + 2 를 O(n²) 이라고 적어도 틀리지 않습니다. n² 도 위에서 덮기 때문입니다.

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

자주 만나는 모양

실무에서 만나는 빅오는 몇 가지 모양으로 모입니다. 모양마다 n 이 두 배가 될 때 일이 어떻게 변하는지를 비교해 봅니다.

표에 로그가 나오므로 먼저 풉니다. log n 은 n 을 몇 번 반으로 나눠야 1 이 되는지를 센 값입니다. 이 값을 구하는 함수가 로그 함수입니다.

16 으로 해 보면 아래처럼 네 번 나눠 1 이 됩니다.

flowchart TD
    A["16"] -->|반으로| B["8"]
    B -->|반으로| C["4"]
    C -->|반으로| D["2"]
    D -->|반으로| E["1"]

화살표가 네 개이니 log 16 은 4 입니다. 백만은 스무 번쯤 나누면 1 이 됩니다. n 이 커져도 log n 은 아주 천천히 자랍니다.

아래 표는 자주 만나는 모양을 일이 덜 불어나는 것부터 차례로 모았습니다.

표의 아래로 갈수록 같은 n 에서 일이 크게 불어납니다. n 이 백만이면 O(log n) 은 스무 단계쯤입니다. O(n²) 은 1조 단계입니다.

이중 반복문이 왜 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 입니다.

n 이 4 이면 쌍이 아래처럼 쌓입니다. 바깥 반복이 한 칸 나아갈 때마다 줄이 하나씩 짧아집니다.

flowchart TD
    subgraph R0["i = 0 · 비교 3번"]
        P01["a[0]·a[1]"]
        P02["a[0]·a[2]"]
        P03["a[0]·a[3]"]
    end
    subgraph R1["i = 1 · 비교 2번"]
        P12["a[1]·a[2]"]
        P13["a[1]·a[3]"]
    end
    subgraph R2["i = 2 · 비교 1번"]
        P23["a[2]·a[3]"]
    end
    R0 --> R1 --> R2

비교는 3 + 2 + 1 로 6 번입니다. 식에 4 를 넣은 4 × 3 / 2 도 6 입니다.

n(n-1)/2 를 풀어 쓰면 n²/2 − n/2 입니다. 작은 항과 곱해진 1/2 을 지우면 O(n²) 입니다.

n 과 n² 을 한 그림에 그리면 차이가 모양으로 보입니다. 바닥 가까이 곧게 오르는 선이 n 입니다. 휘어지며 가파르게 솟는 선이 n² 입니다.

xychart-beta
    title "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 번 비교합니다.

그래서 비용을 셋으로 나눠 말합니다. 아래 표는 세 경우의 뜻과 순차 탐색에서 드는 비교 횟수입니다.

빅오는 셋 가운데 어느 하나에 묶인 표기가 아닙니다. 셋은 저마다 n 에 따라 변하는 함수입니다. 빅오는 그중 어느 함수에든 붙일 수 있습니다. 순차 탐색이라면 최선은 O(1), 최악은 O(n) 입니다.

해시테이블 조회를 「평균 O(1), 최악 O(n)」이라고 적는 것도 같은 방식입니다. 경우를 밝히지 않고 O(n) 이라고만 쓰면 대개 최악의 경우를 두고 하는 말입니다. 최악을 알면 어떤 입력이 와도 그보다 오래 걸리지 않는다고 말할 수 있기 때문입니다.

아래에서 받치는 선과 양쪽을 묶는 선

빅오는 위에서 덮는 선만 적습니다. 아래에서 받치는 선과 위아래를 한꺼번에 묶는 선에는 따로 이름이 있습니다.

빅오메가 표기법은 하한을 나타냅니다. Ω(g(n)) 으로 적습니다. n 이 커진 뒤로 f(n) 이 c·g(n) 아래로 내려가지 않는다는 뜻입니다.

빅세타 표기법은 위아래를 같은 모양으로 묶습니다. Θ(g(n)) 으로 적습니다. 같은 g(n) 으로 빅오와 빅오메가가 함께 성립할 때 씁니다.

「위에서 덮는 선」의 세 선 그림이 그 예입니다. n + 2 는 아래에서 n 이 받칩니다. 위에서는 2n 이 덮습니다. 받치는 선과 덮는 선이 모두 n 의 모양이므로 n + 2 = Θ(n) 입니다.

앞 소절에서 경우를 밝히지 않은 O(n) 은 대개 최악의 경우를 두고 하는 말이라고 했습니다. 실무에서는 그 최악의 경우를 덮는 선 가운데 가장 낮은 것을 골라 말합니다. 가장 낮은 선을 고르면 대개 아래에서도 받치게 됩니다.

그래서 「이 코드는 O(n) 이다」는 대개 「최악의 경우가 Θ(n) 이다」라는 뜻입니다. 교재와 논문은 둘을 가려 씁니다.

메모리에도 쓰는 표기

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

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

메모리를 더 쓰고 시간을 줄이는 선택도 흔합니다. 해시테이블이 값을 담을 칸을 넉넉히 잡아 두고 조회를 O(1) 로 만드는 것이 그렇습니다. 이런 선택이 시간과 공간 맞바꿈입니다.

빅오가 지우는 비용

빅오는 곱해진 수와 작은 항을 버립니다. 버린 것 가운데 실무에서 크게 돌아오는 것이 둘 있습니다.

첫째는 작은 n 입니다. O(n log n) 정렬도 원소가 몇 개 안 될 때는 삽입 정렬 같은 O(n²) 방법보다 늦게 끝나기도 합니다. n 이 작으면 버린 곱해진 수와 준비 작업이 전체를 좌우하기 때문입니다.

둘째는 한 단계의 무게입니다. 빅오는 단계마다 드는 시간을 같다고 봅니다. 메모리에서 값 하나를 읽는 것과 데이터베이스에 쿼리를 한 번 보내는 것이 똑같이 한 단계입니다. 네트워크를 한 번 오가는 왕복 시간은 메모리 읽기보다 훨씬 깁니다.

주문 n 건을 가져온 뒤 건마다 상세를 가져오는 쿼리를 하나씩 더 보내면 쿼리가 n + 1 번 나갑니다. 이것이 N+1 문제입니다. 아래 그림은 앱과 데이터베이스 사이를 오가는 순서입니다.

sequenceDiagram
    participant 앱
    participant 데이터베이스
    앱->>데이터베이스: 주문 목록 쿼리
    데이터베이스-->>앱: 주문 n 건
    loop 주문마다
        앱->>데이터베이스: 그 주문의 상세 쿼리
        데이터베이스-->>앱: 상세
    end
    Note over 앱,데이터베이스: 합쳐 n + 1 번 왕복

목록 쿼리 한 번 뒤에 주문마다 왕복이 한 번씩 더 붙습니다. 반복문 하나짜리 O(n) 이라도 한 번에 무엇을 하느냐에 따라 걸리는 시간이 크게 갈립니다.

그래서 무엇을 한 단계로 셀지부터 정합니다. 쿼리 수나 디스크 읽기 횟수처럼 가장 비싼 동작만 따로 세어 빅오로 적기도 합니다.

빅오로 가르는 때와 재 보는 때

빅오가 힘을 쓰는 때는 데이터가 자라는 코드를 볼 때입니다. 지금은 백 건이지만 앞으로 백만 건이 될 테이블을 다루는 코드라면 빅오가 미리 경고를 줍니다. 자료구조를 고를 때나 코드 리뷰에서 반복문 안의 반복문을 만났을 때가 그렇습니다.

n 이 작고 늘 일정하면 빅오로 가를 것이 별로 없습니다. 그때는 프로파일링이나 벤치마크로 걸리는 시간을 직접 잽니다. 빅오는 데이터가 커질 때 어느 쪽이 버티는지를 알려 줍니다. 지금 몇 초 걸리는지는 재 봐야 압니다.

관련 항목

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

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

빅오 표기법으로 적는 비용

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

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

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

빅오 표기법으로 비용을 적는 알고리즘과 자료구조

알고리즘 · 자료구조 · 순차 탐색 · 이진 탐색 · 병합 정렬 · 삽입 정렬 · 정렬 · 배열 · 해시테이블 · 이진 탐색 트리 · 심볼 테이블

빅오 표기법이 상수로 지우는 비용

왕복 시간 · N+1 문제 · 참조 지역성 · CPU 캐시 · 디스크 입출력 · 캐시 미스

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

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

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

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