250906 - Asymptotic bound

알고리즘 넘 어렵다~.~ 내일은 과제하쟈

 

Asymptotic bound (점근 표기법)

알고리즘의 수행 시간을 표기하기 위해, 필수적인 부분에 집중하고 불필요한 상세들은 무시한다.

알고리즘의 시간적, 공간적, 성능과 효율을 측정해야 한다.

 

대표적으로 Big- Θ, Big -Ω, Big - O표기법이 있다.

 

Big- Θ

상한과 하한을 둘 다 알고 있을 때 사용하는 표기법이다.

 

 Big -Ω

점근적 하한만 알고 있을 때 사용하는 표기법이다.

즉 아무리 빨라도 이 기준보다 빠를 수 없다.

 

Big - O

점근적 상한만 알고 있을 때 사용한다, 즉 최악의 경우에도 이 기준을 넘을 순 없다.

asymptotic upperbound(점근적 상한선) 을 의미한다.

 

If there exists two numbers M >= 0 and x0 such that f(x) <= Mg(x) for all x > x0, then we way f(x) = O(g(x))

양의 실수인 x0보다 큰 x에 대해서 0 <= f(x) <= Mg(x)를 만족시키는 상수 M이 존재한다.