The Big Oh Notation

상위 문서: 알고리즘 설계와 분석

개요

주어진 어떤 알고리즘에 대한 시간 복잡도는 가능한 문제 인스턴스 크기에 대한 함수들이며, 이들을 정밀하게 다루는 것은 매우 어렵다. 따라서 이들을 단순화하여 분석하는 것이 매우 좋은 방식 중 하나이다. 예를 들어, $T(n)=12754n^2+4353n+834lo{g}_2^n+13546$와 같은 시간 복잡도 함수는 정밀하게 분석하기란 매우 어렵지만, 시간 복잡도가 n에 대해 2차적으로 증가한다는 관찰이 틀렸다고 볼 수는 없다.

해당 문서에서는 이러한 특성을 이용한 “빅 오(Big Oh)” 표기에 대해 알아본다.

내용

Figure 1. Big Oh, Omega, Theta

“빅 오(Big Oh)” 표기는 시간 복잡도 함수를 상한/하한으로 나타내어 이를 단순화 하는 방식이다. 함수 $f(n)=2n$과 $g(n)=n$은 빅 오 분석에서 동일하다. 빅 오 표기에는 아래와 같은 세 가지 정의가 존재한다.

• $f(n)=O(g(n))$는 $c\cdot g(n)$가 $f(n)$에 대한 상한임을 의미한다.
  • 따라서 어떤 상수 c가 존재하여 충분히 큰 모든 n에 대하여 $f(n)\le c\cdot g(n)$가 성립한다.
• $f(n)=\mathrm{\Omega }(g(n))$는 $c\cdot g(n)$가 $f(n)$에 대한 하한임을 의미한다.
  • 따라서 어떤 상수 c가 존재하여 충분히 큰 모든 n에 대하여 $f(n)\ge c\cdot g(n)$가 성립한다.
• $f(n)=O(g(n))$는 $c_1\cdot g(n)$가 $f(n)$에 대한 상한이고 $c_2\cdot g(n)$가 $f(n)$에 대한 하한임을 의미한다.
  • 따라서 어떤 상수 c₁, c₂가 존재하여 충분히 큰 모든 n에 대하여 $c_2\cdot g(n)\le f(n)\le c_1\cdot g(n)$가 성립한다.

이러한 정의들은 figure 1에 잘 제시되어 있다. 이들 정의 각각은 어떤 상수 n₀가 존재하여 그 이후에는 조건이 만족된다는 것을 보여준다.

Working with the Big Oh

일반적인 대수 계산을 빅 오 표기에 적용하는 것은 중요하면서도 조금 모호하다. 이는 대부분의 대수 계산에 대한 상식이 유지되면서도 꼭 모두 적용된다고는 말할 수 없기 때문이다.

Big Oh Addition/Subtraction

어떠한 차수가 같은 함수 $f(n),g(n)$에 대해 $f(n)=O(n^2),g(n)=O(n^2)$를 가정해 보자. 이때 함수 $g^{\prime }(n)=f(n)+g(n)$에 대한 빅 오 표기는 아래와 같이 계산할 수 있다.

$f(n)\le c_1\cdot n^2,g(n)\le c_2\cdot n^2$이라 하면
$g^{\prime }(n)=f(n)+g(n)\le (c_1+c_2)n^2,\therefore g^{\prime }(n)=O(n^2)$

즉, 같은 차수의 함수끼리 더해도 결국 그 차수는 변하지 않는다. 하지만 빅 오 표기에서의 뺄셈은 최대 차수의 계수에 따라 그 결과가 달라지기 때문에, 모호하게 작동한다. 예를 들어 함수 $g^{″}(n)=f(n)-|g(n)|$에 대해:

$f(n)=n^2,g(n)=n^2$이라면 , $f(n)-g(n)=0$
$f(n)=2\cdot n^2,g(n)=n^2$이라면, $f(n)-g(n)=n^2$

따라서 어떤 차수가 같은 함수 $f(n),g(n)$에 대해 뺼셈을 진행한다면, 일반적으로 $O(n^2)$라고 말할 수 있을 뿐이며, 해당 차수가 보존되는 지에 대해서는 말할 수 없다.

Multiplying Functions

곱셈은 반복된 덧셈과 같이 취급할 수 있다. 따라서, $c>0$를 만족하는 상수 c에 대해 아래와 같이 계산된다.

$O(c\cdot g(n))\to O(g(n))$
$\mathrm{\Omega }(c\cdot g(n))\to \mathrm{\Omega }(g(n))$
$\mathrm{\Theta }(c\cdot g(n))\to \mathrm{\Theta }(g(n))$

하지만 증가함수인 두 함수를 서로 곱하는 경우에는, 두 함수가 모두 결과에 준다. 이는 아래와 같이 나타낼 수 있다.

$O(f(n))\cdot O(g(n))\to O(f(n)\cdot g(n))$
$\mathrm{\Omega }(f(n))\cdot \mathrm{\Omega }(g(n))\to \mathrm{\Omega }(f(n)\cdot g(n))$
$\mathrm{\Theta }(f(n))\cdot \mathrm{\Theta }(g(n))\to \mathrm{\Theta }(f(n)\cdot g(n))$

Reasoning about Efficiency

알고리즘의 실행 시간에 대한 추론은 보통 쉽다. 이에 대한 예시는 Sorting Problem에 대한 문서를 참조하면 된다.

Growth Rates and Dominance Relations

Figure 2. Asymptotic Dominance in Action

빅 오 표기를 사용하면 분석할 시간 복잡도 함수들의 계수들을 버릴 수 있다. 따라서 $f(n)=0.001n^2,g(n)=1000n^2$는 동일하게 취급된다. 이는 다소 거칠게 보일 수 있지만, 이는 상당히 유용하다. 그 이유는 figure 2에 나타나 있는 도표를 통해서 해당 알고리즘의 빅 오 표기를 통해서 해당 알고리즘의 실용성을 판단할 수 있기 때문이다. 해당 표에서는 아래와 같은 결론을 도출할 수 있다.

• n = 10일 때에는 거의 모든 알고리즘이 동일한 시간을 소요한다.
• 실행 시간이 O(n!)인 모든 알고리즘은 n ≥ 20일 때 사실상 의미가 없다.
• 실행 시간이 O(n²)인 모든 알고리즘들은 n > 40일 때 비실용적이다.
• 실행 시간이 O(n^²)인 모든 알고리즘들은 n=10,000 까지는 사용 가능하지만, 이를 초과하면 급격히 나빠진다.
• 실행 시간이 O(n$log$n) 이하인 모든 알고리즘들은 10억 개 항목의 입력에서도 여전히 실용적이다.

즉, 이는 분석할 시간 복잡도 함수들의 계수들을 무시하더라도, 주어진 크기의 문제에 대해 주어진 알고리즘이 적절한지에 대한 판단을 할 수 있다는 것이다.

Dominance Relations

함수 $f(n)$는 함수 $g(n)$를 아래와 같은 상황에 대하여 지배한다고(dominate) 한다.

$li{m}_{n\to \mathrm{\infty }}g(n)/f(n)=0$
이 경우, $g(n)=o(f(n))$과 같이 표기한다.

아래는 각 함수에 대한 지배 관계를 나타낸 것이다:

$n!\gg 2^n\gg n^3\gg n^2\gg n\cdot log(n)\gg n\gg log(n)\gg 1$

이때 주의할 점은 로그에서의 밑은 중요하지 않다는 것이다. 그 이유는 아래와 같은 수학 공식이 성립하기 때문이다:

$lo{g}_{b}a=\frac{lo{g}_{c}b}{lo{g}_{c}a}$

즉, 로그의 밑을 바꾸는 것은 단순히 계수에 영향을 주기 때문에 무시할 수 있다.