빅오 표기법과 복잡도

자료 1000개를 처리하는 데 0.01초 걸리는 프로그램이 있다. 자료가 100만 개로 1000배 늘면 몇 초가 걸릴까? 10초라고 답하기 쉽다. 그런데 어떤 프로그램은 0.02초로 거의 그대로이고, 어떤 프로그램은 3시간 가까이 걸리며, 어떤 프로그램은 끝나지 않는다. 같은 자료에 같은 컴퓨터인데 왜 이렇게 다를까? 연산 횟수가 늘어나는 빠르기를 한 글자로 요약하는 방법이 있다.

입력의 크기 n

3.6.1빅오 표기법

알고리즘의 실행 시간은 컴퓨터의 빠르기, 언어, 코드의 세부에 따라 달라진다. 그래서 알고리즘을 견줄 때는 시간 자체보다 입력의 크기 \(n\)이 커질 때 연산 횟수가 얼마나 빠르게 늘어나는지를 본다. 연산 횟수가 \(3n^2 + 5n + 7\)이라면 \(n\)이 클 때 \(n^2\) 항이 나머지를 압도하고, 앞의 상수 3은 컴퓨터를 바꾸면 달라지는 값이다. 그래서 가장 빨리 자라는 항만 남기고 상수를 버려 \(O(n^2)\)으로 쓴다. 이것을 빅오 표기법이라 하며, 알고리즘의 시간 복잡도를 나타낸다.

그림 1에서 \(n\)을 바꾸어 보자. \(n = 100\)만이면 \(O(\log n)\)은 20번이라 눈 깜짝할 사이이고, \(O(n)\)은 0.01초, \(O(n\log n)\)은 0.2초이다. 그런데 \(O(n^2)\)은 \(10^{12}\)번으로 약 2.8시간이 걸리고, \(O(2^n)\)은 \(n = 100\)만 되어도 우주의 나이보다 길다. 처음 질문의 프로그램이 1000개에서 0.01초였다면, \(O(n)\)은 10초, \(O(n\log n)\)은 20초, \(O(n^2)\)은 약 2.8시간이 된다. 그래서 큰 자료를 다룰 때는 컴퓨터를 바꾸는 것보다 복잡도가 낮은 알고리즘을 고르는 것이 훨씬 효과가 크다.¹

3.6.2코드에서 복잡도 읽기

코드를 보고 복잡도를 어림할 수 있다. 리스트를 한 번 훑는 반복문은 \(O(n)\)이고, 반복문 안에 같은 크기의 반복문이 또 있으면 \(O(n^2)\)이다. 범위를 반씩 줄이며 반복하면 \(O(\log n)\)이다. 재귀는 호출이 만드는 나무의 크기를 세어야 하는데, 피보나치처럼 호출마다 두 갈래로 갈라지면 \(O(2^n)\)에 가깝다. 그리고 반복문 안에서 쓰는 함수의 비용도 함께 세야 한다. 리스트의 pop(0)이나 in 검사는 원소 수만큼 걸리므로, 반복문 안에서 쓰면 \(O(n)\)이 \(O(n^2)\)이 된다. 메모리를 얼마나 쓰는지도 같은 방법으로 공간 복잡도로 나타낸다.

3.6.3예제 풀이

(가)는 \(\dfrac{n(n-1)}{2}\)쌍을 견주므로 \(O(n^2)\)이다. 원소가 1000배이면 시간은 \(1000^2 = 100\)만 배인 약 5000초, 곧 1시간 20분 남짓이다.

(나)는 정렬에 \(O(n\log n)\), 이웃끼리 견주기에 \(O(n)\)이므로 전체가 \(O(n\log n)\)이다. 원소가 1000배이면 \(n\log n\)은 \(1000 \times \dfrac{\log 10^6}{\log 10^3} = 1000 \times 2 = 2000\)배이므로 약 10초이다. 같은 일을 하는 두 방법이 500배 차이 난다. 즉 빅오는 프로그램이 큰 자료에서 어떻게 될지 미리 알려 주는 도구이다. 그래서 코드를 짜기 전에 복잡도부터 어림해 보고, 감당할 수 없는 방법은 처음부터 고르지 않는다.

아래 탐구 카드에서 여러 알고리즘의 연산 횟수를 세어 빅오로 나타내고, 입력 크기를 바꾸며 실행 시간을 견주어 보자.

1. 빅오 표기법은 1890년대 독일의 수학자 바흐만과 란다우가 수론에서 함수의 증가 속도를 나타내려고 쓰기 시작했고, 1970년대 크누스가 알고리즘 분석에 널리 퍼뜨렸다.