본문 바로가기

Programming

점근적 표기

반응형

f(),g() 는 함수이며, c는 상수이다.

θ(세타) :  g(n)을 f(n)의 점근적으로 정확한 한계(asymptotically tight bound)
θ(g(n)) = {f(n) : 모든 n>=n0에 대해 0<=c1g(n)<=f(n)<=c2g(n)인 양의 상수 c1, c2, n0이 존재 한다}

Ο(빅-오, 오) : 점근적 상한
Ο(g(n)) = {f(n) : 모든 n>=n0 에 대해 0<=f(n)<=cg(n)인 양의 상수 c, n0이 존재한다}

Ω(빅-오메가, 오메가) : 점근적 하한
Ω(g(n)) = {f(n) : 모든 n>=n0 에 대해 0<=cg(n)<=f(n) 인 양의 상수 c,n0이 존재한다}

ο(리틀-오) : 점근적으로 여유있는 상한
ο(g(n)) = {f(n) : 임의의 양의 상수 c>0 에 대해 그리고 모든  n>=n0 에 대해 0<=f(n)<=cg(n)인 양의 상수 n0 이 존재한다}

ω(리틀-오메가) : 점근적으로 여유있는 하한
ω(g(n)) = {f(n) :  임의의 양의 상수 c>0 에 대해 모든 n>=n0에 대해 0<=cg(n)<f(n)인 양의 상수 n0이 존재한다}

반응형

'Programming' 카테고리의 다른 글

루프 불변성 ( loop invariant )  (0) 2009.04.04
UpCasting & DownCasting  (3) 2009.03.30
배열 참조와 2차원 배열의 선언  (0) 2009.03.24
배열 선언, 복사  (0) 2009.03.24
퀵정렬(quick sort)  (0) 2009.03.19