Did you know that you can navigate the posts by swiping left and right?

5. 빅-오 표기법에 대해서

빅-오 표기법 (Big-Oh Notation)

함수 \(T(n)\) (시간 복잡도 함수)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것이다. 이때 사용되는 표기법에 대문자 \(O\)가 사용되기 때문에 빅-오(Big-Oh)라고 불린다.

\(T(n)\)이 다항식으로 표현된 경우, 최고차항의 차수가 빅-오가 된다.

예를 들어보자. 열심히 \(T(n)\)을 구해봤는데, 만약 결과가

\[ T(n) = 7n^2 + 2n + 1 \]

이었다면, 빅-오 표기법으로 표현하면 다음과 같다.

\[ O(n^2) \]

너무 단순해지긴 했지만, 그렇다. 계수도 필요없고, 뒤의 \(2n + 1\)같은 ~~찌끄레기~~ 것들도 필요없다. \(O(n^2)\)은 “빅-오 오브 \(n^2\) (Big-Oh of \(n^2\))”라고 부른다.

\[ 3n + 2 = O(n) \]

\[ 7n^3 + 3n^2 + 2 = O(n^3) \]

\[ 2^n + n^2 = O(2^n) \]

\[ n + \log n = O(n) \]

\[ n + n\log n = O(n\log n) \]

\[ \Large 2^n + n^3 = O(2^n) \]

위의 예시를 보면, 빅-오 표기법에 대해서 잘 알 수 있다. 2개의 항 중에 어떤 것을 택해야할지 모르겠다면, 증가율이 가장 큰 것으로 고르면 된다. 예를 들어 보자.

\[ 2^n + n^2 \]

\(2^n\)을 택해야할지 \(n^2\)을 택해야할지 고민일 수 있다. 이럴 때 \(n\)에 숫자를 대충 집어넣어보면 된다. (이왕이면 큰 숫자로..)

\[ n = 5, 2^5 = 32, 5^2 = 25 \]

\[ n = 10, 2^{10} = 1024, 10^2 = 100 \]

\[ n = 15, 2^{15} = 16384, 15^2 = 225 \]

더 이상 비교하지 않아도, \(2^n\)의 증감률이 더 크다는 것을 알 수 있다. 이렇게, \(n\)에 대충 값을 집어넣으면 알 수 있다.

\[ O(l) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) \]

이 되는데, O(l)이 뭐냐면, 연산횟수가 고정인 유형의 알고리즘을 의미한다. (무조건 3번만 수행한다던가 그런 특수한 알고리즘을 의미한다.)

빅-오의 수학적 정의는 다음과 같다.

두 개의 함수 \(f(n)\)과 \(g(n)\)이 주어졌을 때, 모든 \(n \ge K\)에 대하여 \(f(n) \le Cg(n)\)을 만족하는 두 개의 상수 \(C\)와 \(K\)가 존재하면, \(f(n)\)의 빅-오는 \(O(g(n))\)이다.

예시를 들어서 설명해보자.

두 개의 함수가 주어졌을 때, \(f(n) = 9n^2 + 7\)이고 \(g(n) = 8n^2\)이라고 해보자.
모든 \(n \ge K\)에 대하여 모든 \(n \ge 800\)에 대하여, ~~\(n\)에는 겁나 큰 숫자를 넣는 것을 추천하는 바이다.~~
\(f(n) \le Cg(n)\)을 만족하는 두 개의 상수 \(C\)와 \(K\)가 존재하면 \(9n^2 + 7 \le 999 \times 8n^2\)을 만족하는 999\(C\)와 800\(K\)이 존재하니, (C 자리에도 이왕이면 큰 수를 집어넣는 것이 좋다.)
\(f(n)\)의 빅-오는 \(O(g(n))\)이다. \(9n^2 + 7\)의 빅-오는 \(O(n^2)\)이다.

빅-오라는 개념은 증가율의 상한선을 표현하는 표기법이다. 쉽게 말하자면, 함수가 극한으로 갈 때, 어떤 함수가 가장 큰지, 어떤 함수보다 작은 지를 비교하는 기준으로 쓰인다는 것이다. 고로, 빅-오라는 개념에서 볼 때, \(n\)의 값이 얼마인지는 중요하지 않다.

Coding Future, Decoding Society.