[자료구조] 차수 표기법

 
- 차수 표기법(order notation)

O-표기법 (상한)
  n≥n0인 모든 n에 대해 T(n) £ c×f(n)을 만족하는 0보다 큰 상수

  c와 n0가 존재하면, T(n) = O(f(n))으로 나타낸다.

Ω-표기법 (하한)
  n≥n0인 모든 n에 대해 T(n) ≥ c×f(n)을 만족하는 0보다 큰 상수

  c와 n0가 존재하면, T(n) = W(f(n))으로 나타낸다.

в-표기법 (정확)
  n≥n0인 모든 n에 대해 c1×f(n) £ T(n) £ c2×f(n)을 만족하는 0보다

  큰 상수 c1, c2, n0가 존재하면, T(n) = Q(f(n))으로 나타낸다.