[컴퓨터알고리즘] 3장 - 함수의 증가

Asymptotic Analysis 점근적 분석

- Order of growth가 관심사.

- 이론적으로 수행 시간을 분석: n에 대한 함수로 알아낸다. 최고차항이 결정.

- 시간복잡도 비교: 1 << logn << n << nlogn << n^2 << n^3 << 2^n << n!

 

Asymptotic Notations 점근적 표기

- Big-Oh, Big-Omega, Theta, small-oh, small-omega

 

Big O: f(n) = O(g(n))이면 g(n)은 f(n)의 상한. upper bound.

small o: f(n) = o(g(n))이면 f(n)은 g(n)보다 느리다

Big Ω: f(n) = Ω(g(n))이면 g(n)은 f(n)의 하한. lower bound.

small ω: f(n) = ω(g(n)) 이면 f(n)은 g(n)보다 빠르다.

Theta Θ: f(n) = Θ(g(n))이면 f(n)과 g(n)은 증가속도가 같다. tight bound.

 

Monotonicity

f(n)이 단조 증가: m<=n일때 f(m)<=f(n)

f(n)이 단조 감소: m<=n일때 f(m)>=f(n)

같음을 허용하지 않으면 강한 단조 증가/감소(순증가/순감소)

 

로그함수들 - lgn, logn은 증가속도가 같다

지수함수들 - 2^n, 3^n은 증가속도가 다르다