알고리즘 차수 표기법

- Big O 표기법

           = worst와 비슷
           : 점근적 상한
           : 궁극적으로 이것보단 좋다(=기울기가 같거나 낮다)

- Ω 표기법

           : 점근적 하한
           : 아무리 좋아도 이것보다 좋아질 수 없다(=기울기가 높다)

     

- Θ 표기법

            : 점근적 협소
            : 차수가 같다(=기울기가 같다)

 

 - Small o 표기법

            : 차수가 작다(=기울기가 낮다)  
             (같을 수 없다)

---

- 차수의 주요 성질

• g(n) ∈ O(f(n)) <=> f(n) ∈ Ω(g(n))
• g(n) ∈ Θ(f(n)) <=> f(n) ∈ Θ(g(n))
• 로그 복잡도 함수는 모두 같은 카테고리 => Θ(lg n)
• 지수 복잡도 함수는 모두 같은 카테고리 X
  
• n! 는 어떤 지수 복잡도 함수보다 나쁨
• 좋은 것부터 나열

좋은 것 부터 나열

• n  c ≤ 0, d > 0 일 때,
  g(n) ∈ O(f (n)), 그리고 h(n) ∈ Θ(f (n))이면, => g(n)의 차수 ≤ f(n)의 차수 = h(n)의 차수
  c x g(n) + d x h(n) ∈ Θ(f (n)) 가 성립.