Programming2009.03.29 12:10

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이 존재한다}

신고
Posted by 초프(초보 프로그래머)