[자료구조론] 2주차: Notation

Big-O notation

입력의 개수 $n$에 따른 함수의 상한을 표시한 것

 

수학적 정의

두 함수 $f(n)$과 $g(n)$이 주어졌을 때, 모든 $n \geq n_0$에 대해

$\mid f(n)\mid\; \leq \; c\mid g(n) \mid$

을 만족하는 상수

$c$, $n_0$

가 존재하면 $f(n) = O(g(n))$이다.

 

$n$이 어느 정도 커졌을 때 $f(n)$이 $g(n)$보다 항상 작으면 $g(n)$은 $f(n)$보다 연산 횟수가 큰 상한이라는 얘기다.

 

기본 연산 횟수가 다항식일 경우 최고차항만 사용

$8n^2\log{n} + 5n^2 + n$ -> $O(n^2\log{n})$

$10$ -> $O(1)$

 

$O(1) < O(\log{n}) < O(n) < O(n\log{n}) < O(n^2) < O(n^3) < O(2^n) < O(n!)$

($O(1)$: 입력 개수와 관계없이 일정한 횟수의 연산 수행)

 

빅오 표기법: 입력의 개수 $n$에 따른 함수의 상한을 표시한 것

상한은 여러 개가 있을 수 있다

-> 정의에 포함된 내용은 아니나 여러 상한 중 최소차수로 표현하는 것이 일반적 (다른 걸 써도 틀린 건 아님)

 

 

Big-Omega notation

입력의 개수 $n$에 따른 함수의 하한을 표시한 것

 

수학적 정의

두 함수 $f(n)$과 $g(n)$이 주어졌을 때, 모든 $n \geq n_0$에 대해

$\mid f(n)\mid\; \geq \; c\mid g(n) \mid$

을 만족하는 상수

$c$, $n_0$

가 존재하면 $f(n) = \Omega(g(n))$이다.

 

 

Ex) $n \geq 1$에 대해 $2n + 1 \lt n$이므로 $2n + 1 = \Omega(n)$

 

 

Big-Theta notation

입력의 개수 $n$에 따른 함수의 상한과 하한을 동시에 표시한 것

 

수학적 정의

두 함수 $f(n)$과 $g(n)$이 주어졌을 때, 모든 $n \geq n_0$에 대해

$c_1\mid g(n) \mid \; \geq \; \mid f(n)\mid\; \geq \; c_2\mid g(n) \mid$

을 만족하는 상수

$c_1$ $c_2$, $n_0$

가 존재하면 $f(n) = \Theta(g(n))$이다.

 

$f(n) = O(g(n)) = \Omega(g(n))$이면 $f(n) = \Theta(g(n))$이다.

-> $\Theta(g(n))$을 찾으려면 $f(n)$에 대해 상한 $O(g(n))$, 하한$\Omega(g(n))$ 모두 표기가 가능해야 하며,

이런 $g(n)$을 $\Theta(g(n))$으로 표기한다.

 

Ex) Ex) $n \geq 1$에 대해 $n \lt 2n + 1 \lt 3n$이므로 $2n + 1 = \Theta(n)$

 

보통은 $O(g(n))$ 중에서 가장 작은 $g(n)$을 $\Theta(g(n))$라고 한다.

 

 

g(n)은 어떻게 구하는가?

수행 시간은 입력 자료 집합에 따라 다르다.

이 때 수행 시간에 따라 Best case, Average case, Worst case의 세 가지의 g(n)을 구한다.

 

Best case는 별 의미가 없고, Average case는 구하기 어려워서

계산하기 쉽고 유의미한 Worst case를 구하는 것이 일반적이다.