Big-O Notation (빅오 표기법)이란
알고리즘의 복잡도를 나타내는 지표 혹은 언어로 계산 복잡도 이론에서 사용되는 점근 표기법이다. 또한, 란다우 표기법이라고 부르기도 하는데 복잡도 이론, 컴퓨터 과학, 수학에서 함수의 점근적 동작을 설명하기 위해 사용하며, 기본적으로 함수가 얼마나 빠르게 증가 혹은 감소하는지 알려준다. 따라서 Big-O 표기법은 알고리즘의 속도를 파악하는데 큰 도움이 된다.
개념의 비유(시간 복잡도)
만약 우리가 누군가에게 파일을 전달하고자 할 때를 생각해보자. 메일이나 FTP 등 온라인을 통해 상대방에게 파일을 전송할 수도 있고 직접 파일이 담긴 USB를 전달할 수도 있을 것이다. 온라인으로 파일은 전송하는 방법은 간단하고 손쉽다. 하지만 파일 크기가 1TB가 넘는다면? 이러한 경우에는 파일을 전달하는데 하루가 부족할지도 모른다. 파일 크기에 따라 걸리는 시간이 증가하는 것이다. 반면에, 직접 USB에 파일을 담아 전달할 경우, 파일 크기가 얼마나 크던 작던 상관없이 걸리는 시간은 변하지 않는다. 즉, 파일 전달까지 걸리는 시간이 파일 크기에 무관하게 일정한 시간이 걸리는 것이다. 이를 Big-O 표기법으로 나타내면, 온라인 전송의 경우, O(n) (여기서 n은 파일의 크기를 의미한다), 직접 전달의 경우 O(1)로 나타낼 수 있다. 이것이 바로 Big-O 시간에 대한 개념이다.
그 외의 개념 Big-O, Big-Θ, Big-Ω
Big-O : 학계에서 O는 상한을 나타낸다. 어떤 알고리즘은 O(n)으로 표현할 수 있지만, 이 외에 N보다 큰 big-O 시간으로 표현할 수도 있다. 예를 들어 O(n²), O(n³)도 옳은 표현이다. 다시 말해 알고리즘의 수행 시간은 적어도 이들 중 하나보다 빠르기만 하면 된다. 따라서 big-O 시간은 알고리즘 수행 시간의 상한이 되고, 이는 '작거나 같은' 부등호와도 비슷한 관계가 있다. 만약 철수의 나이가 X라면 X ≤ 100이라고 말할 수 있지만, X ≤ 1,000 혹은 X ≤ 1,000,000으로 나타내도 옳은 표기법이다. 수학적으로 이야기해서 이들 모두 참인 표현법이다. 마찬가지로 배열의 모든 값을 출력하는 알고리즘은 O(n)이라고 표현할 수 있을 뿐만 아니라 O(n³) 혹은 O(n) 보다 큰 어떤 수행 시간으로도 표현 가능하다.
Big-Ω : 학계에서 Ω는 등가 개념 혹은 하한을 나타낸다. 배열의 모든 값을 출력하는 알고리즘은 Ω(n)뿐만 아니라 Ω(log(n)) 혹은 Ω(1)로도 표현할 수 있다. 결국, 해당 알고리즘은 Ω 수행 시간보다 빠를 수 없게 된다.
Big-Θ : 학계에서 Θ는 Ω와 O 둘 다를 의미한다. 즉, 어떤 알고리즘의 수행 시간이 O(n)이면서 Ω(n)이라면, 이 알고리즘의 수행 시간을 Θ(n)로 표현할 수 있다.
f(x) = o(g(x))는 f가 g보다 느리게 증가한다는 뜻이며 이는 비교에서 크게 중요하지 않다. Θ와 Ω는 컴퓨터 과학에서 종종 사용되며, 소문자 o는 수학에서는 흔하지만 컴퓨터 과학에서는 흔하지 않다. ω는 거의 사용하지 않는다.
흔히 하는 실수는, Θ를 의미할 때 O를 사용하는 것이다. 예를 들어 힙 정렬은 Θ(n×log(n))라는 의미를 전달하고자 하는 의미로 O(n×log(n))이다.라고 말할 수 있다. 둘 다 맞는 말이지만 Θ(n×log(n))가 더 강한 주장이다. 업계에서 big-O의 의미는 학계에서 Θ의 의미와 가깝다. 이 글에서 아래에 설명하는 개념은 학계에서 Θ의 의미와 가까운 big-O 표기법을 사용하겠다.
공간 복잡도
위에서 살펴본 파일 크기에 따른 전송 시간은 시간에 대한 복잡도였다. 알고리즘에서는 시간뿐만 아니라 공간(메모리)에 대해서도 신경을 써야 한다. 예를 들어, 크기가 n인 배열을 만들고자 한다면, O(n)의 공간이 필요하다. 크기가 n×n인 이중 배열을 만들려면, O(n²)의 공간이 필요하다.
표기방법
big-O를 표기하는 방법은 다음과 같다.
상수항은 무시한다. big-O는 단순히 증가하는 비율을 나타내는 개념이므로, n이 충분히 큰 숫자일 경우, O(n) 코드가 O(1) 코드보다 빠르게 동작하는 것이 가능하다. 이런 이유로 수행 시간에서 상수항을 무시해 버린다. 즉, O(2n)으로 표기되어야 할 알고리즘을 O(n)으로 표기한다. big-O 표기법은 수행 시간이 어떻게 변화하는지 표현해주는 것이므로 O(n)이 언제나 O(2n) 보다 나은 것은 아니다.
예를 들어, T(n) = 4 n²-2n+2의 경우, T(n)은 n²의 비율로 증가하며 이는 T(n) = O(n²)으로 표기할 수 있는 것이다.
지배적이지 않은 항은 무시한다. O(n²+n)과 같은 수식이 있을 때는 어떻게 해야 할까? 우선 O(n²+n²)를 보자, 앞에서 상수항은 무시해도 된다고 언급했다. 따라서 O(n²+n²)은 O(2n²)이고 O(n²)이 된다. 이처럼 마지막 n²을 무시해도 된다면 그보다 작은 n항은 어떨까? 무시해도 된다. 즉, 수식에서 지배적이지 않은 항은 무시해도 된다.
O(n²+n)은 O(n²)이 된다.
O(n+log(n))은 O(n)이 된다.
예를 들어, f(n) = 10 log(n)+5(log(n))³+7n+3 n²+6 n³이라면, 이는 f(n) = O(n³)으로 표기할 수 있다.
하지만 언제나 수식에 합을 생략할 수 있는 것은 아니다. 예를 들어, O(B²+A)는 A와 B 사이에 존재하는 특별한 관계를 알고 있지 않은 이상 하나의 항으로 줄일 수 없다.
다음의 그래프는 흔히 사용되는 big-O 시간의 증가율을 나타낸다.
입력 크기 n에 따른 함수의 연산 수 N에 대한 함수 그래프
알고리즘의 표기 방법
그렇다면 알고리즘에서 어떤 경우에 항을 덧셈으로 표기하고, 어떤 경우에 곱셈으로 표기하는지 알아보자.
for(int a : arrA)
{
print(a);
}
for(int b : arrB)
{
print(b);
}
//A의 일이 완전히 수행되고 난 뒤에 B의 일을 수행한다.위의 알고리즘의 경우, 두 개의 for문이 각각 별개로 작업을 수행한다. 이러한 경우, 두 for문의 수행 시간을 더해야 한다. 즉, O(A+B)가 된다.
for(int a : arrA)
{
for(int b : arrB)
{
print(a + "," +b);
}
}
//A의 각 원소에 대해 B의 일을 수행한다.위의 알고리즘의 경우, 두 번째 for문이 첫 번째 for문에 안에 위치해 있어, 첫 번째 for문이 한 번 수행될 때마다 두 번째 for문이 전체 수행된다. 이러한 경우, 두 for문의 수행 시간을 곱해야 한다. 즉, O(A×B)가 된다.
참고
- 게일 라크만 맥도웰, "코딩 인터뷰 완전분석", 인사이트, 2017년 8월
- 위키백과, 점근 표기법, https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95
- Wikipedia, Big O notation, https://en.wikipedia.org/w/wiki.phtml?title=Big_O_notation
- MIT, Big O notation, http://web.mit.edu/16.070/www/lecture/big_o.pdf