얼마나 빠를까: 빅오 표기법

1초에 10억 단계를 처리한다면, 값 100만 개에 n² 방법은 약 17분, n log n 방법은 0.02초가 걸립니다.

정확한 횟수보다 늘어나는 모양

지금까지는 단계를 정확히 셌습니다. 비교 45번, 교환 4번, 확인 20번 같은 식입니다. 정확한 횟수는 작은 예에서는 쓸모가 있지만, 버블 정렬이 일찍 멈추는지, 피벗을 어떻게 고르는지 같은 세부 사항에 따라 달라집니다. 입력이 커지면 한 가지가 나머지를 모두 압도합니다. n이 커질 때 횟수가 어떤 모양으로 늘어나느냐입니다. 단계가 n²처럼 늘어나는 알고리즘은 아무리 잘 다듬어도 언젠가는 n log n처럼 늘어나는 알고리즘에 집니다.

빅오 표기법은 이 늘어나는 모양을 줄여 쓰는 방법입니다. 어떤 알고리즘이 O(n²)(「빅오 엔 제곱」이라고 읽습니다)라는 것은 n이 클 때 단계 수가 n²에 어떤 상수를 곱한 값을 넘지 않는다는 뜻입니다. 두 가지 규칙만 알면 쉽게 쓸 수 있습니다. 상수 배는 버립니다. 3n도 n/2도 O(n)입니다. 가장 빨리 자라는 항만 남깁니다. 선택 정렬의 비교 횟수 n²/2 − n/2는 O(n²)인데, n이 크면 n² 부분이 거의 전부이기 때문입니다. MIT 6.006 강의도 자료 구조와 정렬을 비교할 때 이처럼 n이 커질 때의 실행 시간으로 비교합니다.

자주 나오는 증가 속도

• O(1), 상수. 일의 양이 n과 상관없습니다. 목록의 첫 값이나 위치를 아는 값 읽기.
• O(log n), 로그. 단계마다 문제가 반으로 줄어듭니다. 이진 탐색. 값 100만 개에 약 20단계.
• O(n), 선형. 값마다 한 번씩 다룹니다. 선형 탐색, 가장 큰 값 찾기, 목록 더하기.
• O(n log n). 병합 정렬, 평균적인 퀵 정렬. 비교 정렬이 할 수 있는 최선.
• O(n²), 이차. 모든 쌍을 봅니다. 최악의 버블·선택·삽입 정렬, 또는 서로 겹친 반복문 두 개.
• O(2ⁿ), 지수. 값이 하나 늘 때마다 일이 두 배가 됩니다. n개 물건의 모든 부분집합 시험하기, 하노이 탑 원판 n개 옮기기.

숫자를 초로 바꾸면

컴퓨터가 1초에 기본 단계를 10억(10⁹)번 한다고 해 봅시다. 프로세서 코어 하나의 대략적인 값으로 무난합니다. 값 100만 개라면 증가 속도마다 이렇게 됩니다. O(log n)은 약 20단계로 1마이크로초에 한참 못 미칩니다. O(n)은 100만 단계, 1밀리초입니다. O(n log n)은 약 2,000만 단계, 0.02초입니다. O(n²)는 10¹²단계, 1,000초로 약 17분입니다. O(2ⁿ)은 끝낼 수 없습니다. 2의 100만 제곱은 30만 자리가 넘는 수입니다. 그래서 알고리즘을 잘 고르는 것이 더 빠른 컴퓨터를 사는 것보다 대개 훨씬 중요합니다. 열 배 빠른 기계는 17분을 1.7분으로 줄이지만, O(n²)에서 O(n log n)으로 바꾸면 50분의 1초로 줄어듭니다.

코드에서 빅오 읽기

코드 모양만 보고 증가 속도를 읽을 수 있을 때가 많습니다. 목록을 한 번 도는 반복문은 O(n)입니다. 목록을 도는 반복문 두 개가 겹쳐 있으면 O(n²)입니다. 바깥 반복 n번마다 안쪽이 많으면 n번 돌기 때문입니다. while (n > 1) n = Math.floor(n / 2)처럼 수를 매번 반으로 줄이는 반복문은 O(log n)입니다. 1,000에서 시작하면 9번, 100만에서 시작하면 19번 돕니다. 차례로 일어나는 단계는 더해지고, 큰 항이 이깁니다. O(n) 반복문 다음에 O(n²) 반복문이 오면 전체는 O(n²)입니다.

// O(n): one pass
let total = 0;
for (const x of list) total += x;

// O(n²): every pair
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++)
    if (list[i] === list[j]) console.log("duplicate", list[i]);

// O(log n): halving
let k = list.length, rounds = 0;
while (k > 1) { k = Math.floor(k / 2); rounds++; }

가장 좋은 경우, 평균, 가장 나쁜 경우

같은 알고리즘이라도 입력에 따라 아주 다르게 움직일 수 있습니다. 삽입 정렬은 이미 정렬된 목록에서는 O(n), 거꾸로 된 목록에서는 O(n²)입니다. 퀵 정렬은 평균 O(n log n)이고, 피벗이 계속 나쁘면 O(n²)입니다. 어느 경우인지 말하지 않고 빅오 하나만 말할 때는 보통 최악의 경우를 뜻합니다. 그보다 나빠지지는 않는다는 보장이기 때문입니다. 빅오가 빠뜨리는 것도 있습니다. 상수 배를 무시하므로 입력이 작을 때는 단계가 아주 간단한 O(n²) 방법이 O(n log n) 방법보다 빠를 수 있습니다. 그래서 실제 정렬 함수 중에는 목록의 짧은 조각에서 삽입 정렬로 바꾸는 것이 많습니다.