점근표기법

 

 

• Θ-notation
  • 주어진 함수 g(n)의 집합을 Θ(g(n)) 이라 할 때, (c1, c2은 상수, n 은 양의 수라고 가정한다)+) 상수 또한 0차수 다항식이므로 O(1)로 표기 할 수 있다.
  • C1g(n) ≤ f(n) = Θ(g(n)) ≤ C2g(n) 샌드위치처럼 놓여있는 경우
  • 함수에 대한 점근적 상한, 하한이 존재
• O-notation
  • ( big -O )0 ≤ f(n) = O(g(n)) ≤ cg(n) ( c, n 은 양의 수 )집합의 관점으로 보자면 Θ(g(n)) ⊆ O(g(n)) 라고 볼수 있다.
  • O표기법은 모든 입력에 대한 실행시간에 적용된다. 하지만 Θ 표기법은 모든 입력에서 바인딩되진 않는다.
  • f(n) = Θ(g(n)) 는 f(n) = O(g(n))를 의미한다. (Θ 표기법이 가장 강력하다, O 표기를 남용이라 볼 수 있다.)
  • 점근적 상한만 있을때 사용 (Worst-Case)
• o-notaion (little -o)
  • 2n = o(n^2), 2n^2 ≠ o(n^2)하지만 little o는 f(n) = o(g(n)), 0≤ f(n) < cg(n) 이고 모든 상수 c > 0에 성립한다.
  • big O와의 차이점 : f(n) = O(g(n)) 일때 0 ≤ f(n) ≤ cg(n) 이고 어떤 상수 c > 0 에 성립한다.
  • 점근적으로 조이지 않은 상한을 나타낸다.
• Ω-notation (omega)
  • 0 ≤ cg(n) ≤ f(n) = Ω(g(n))
  • 점근적 하한만 있을때 사용
• w-notiation (little omega)
  • 점근적으로 조이지 않는 하한을 나타낸다.
  • n^2/2 = w(n), n^2/2 ≠ w(n^2)

 

 

점근적표기법을 위와 같이 생각할수 있지만 이 비교법이 항상 통하는 것은 아닙니다.

n 1+sin n의 경우 0과 2사이에서 진동하기 때문 입뉘다.