The Big Oh Notation 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]


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

“빅 오(Big Oh)” 표기는 시간 복잡도 함수를 상한/하한으로 나타내어 이를 단순화 하는 방식이다. 빅 오 표기는 곱셈 상수들 간의 차이를 무시한다. 함수 <math>f(n) = 2n</math>과 <math>g(n) = n</math>은 빅 오 분석에서 동일하다. 빅 오 표기에는 아래와 같은 세 가지 정의가 존재한다.
* <math>f(n) = O(g(n))</math>는 <math>c\cdot g(n)</math>가 <math>f(n)</math>에 대한 상한임을 의미한다.
** 따라서 어떤 상수 c가 존재하여 충분히 큰 모든 n에 대하여 <math>f(n) \le c \cdot g(n)</math>가 성립한다.
* <math>f(n) = \Omega(g(n))</math>는 <math>c\cdot g(n)</math>가 <math>f(n)</math>에 대한 하한임을 의미한다.
** 따라서 어떤 상수 c가 존재하여 충분히 큰 모든 n에 대하여 <math>f(n) \ge c \cdot g(n)</math>가 성립한다.
* <math>f(n) = O(g(n))</math>는 <math>c_1\cdot g(n)</math>가 <math>f(n)</math>에 대한 상한이고 <math>c_2\cdot g(n)</math>가 <math>f(n)</math>에 대한 하한임을 의미한다.
** 따라서 어떤 상수 c<sub>1</sub>, c<sub>2</sub>가 존재하여 충분히 큰 모든 n에 대하여 <math>c_2 \cdot g(n) \le f(n) \le c_1 \cdot g(n)</math>가 성립한다.
이러한 정의들은 figure 1에 잘 제시되어 있다. 이들 정의 각각은 어떤 상수 n<sub>0</sub>가 존재하여 그 이후에는 조건이 만족된다는 것을 보여준다. 

==각주==