[알고리즘 복잡도 분석] Asymptotic notation

알고리즘의 복잡도 분석에 사용되는 notation에는 5가지가 있다. 알고리즘 수업에서도 나오고, 자료구조 수업에서도 나와서 하나로 정리를 해 본다 ^0^ 

수학적으로 완전한 설명은 아니다 ~~ 수학적 정의나 이런 것들은 그냥 참고로만 넣음 이산수학에서 했던 거 같은데 걍 노잼이고 귀찮아

 

1. Big-O Notation

• $O(f(n))$ : 최고차항의 차수가 $f(n)$보다 작거나 같은 함수의 집합

  • 점근적 상한

  • $f(n) \in O(g(n))$

    • 편의를 위해 $f(n) = O(g(n))$ 이라고도 쓴다.(순서)

    • $f$가 점근적으로 $g$보다 작거나 같다.

• Formal Definition

  • 어떤 $c>0$와 $n_0\geq 0$가 있어서 $n\geq n_0$인 모든 $n$에 대해 $f(n)\leq cg(n)$가 성립하는 경우

  • $O(g(n)) = \{f(n) | \exists c.0, n_0\geq 0 s.t. \forall n\geq n_0, f(n) \leq cg(n)\}$

  • 상수 하나만 곱하면 크거나 같아질 수 있는 경우

    • (예시) $an^2 + bn + c = O(n^2)$

      • $c=a+|b|+|c| , n_0=1$

 

2. Big-Omega Notation

• $\Omega(f(n))$: 최고차항의 차수가 $f(n)$보다 크거나 같은 모든 함수

  • 점근적 하한

  • $f(n) \in \Omega (g(n))$

    • 편의를 위해 $f(n) = \Omega (g(n))$ 이라고도 쓴다.(순서)

    • $f$가 점근적으로 $g$보다 크거나 같다.

[여기가 왜 비지 ;;]

 

 

• Formal Definition

  • 어떤 $c>0$와 $n_0\geq 0$가 있어서 $n\geq n_0$인 모든 $n$에 대해 $f(n)\geq cg(n)$가 성립하는 경우

  • $O(g(n)) = \{f(n) | \exists c.0, n_0\geq 0 s.t. \forall n\geq n_0, f(n) \geq cg(n)\}$

  •  상수 하나만 곱하면 작거나 같아질 수 있는 경우

 

3. Big-Theta Notation

• $\Theta (f(n))$: 최고차항의 차수가 $f(n)$과 같은 모든 함수

  • 편의를 위해 $f(n) = \Theta (g(n))$ 이라고도 쓴다.(순서)

  • $f(n) \in \Theta (g(n))$

    • $f$가 점근적으로 $g$와 같다.

    • $O(f(n)) \cap \Theta (f(n))$

 

4. Little-o Notation

• $o(f(n))$ : 최고차항의 차수가 $f(n)$보다 작은 함수의 집합

  • $f(n) \in o(g(n))$

    • $f$가 점근적으로 $g$보다 작다.

  • g가 f의 little o이면 g는 또한 big O이다.

• Formal Definition

  • $o(g(n)) = \{ f(n) | lim_{n \to \infty} = 0 \}$

  • $o(g(n)) = \{f(n) | \exists n_0> 0 s.t. \forall c>0 and \forall n\geq n_0, f(n) > cg(n)\}$

5. Little-omega Notation

• $o(f(n))$ : 최고차항의 차수가 $f(n)$보다 큰 함수의 집합

  • $f(n) \in \omega (g(n))$

    • $f$가 점근적으로 $g$보다 크다.

  • g가 f의 little omega 이면 g는 또한 Big Omega 이다.

• Formal Definition

  • $\omega (g(n)) = \{ f(n) | lim_{n \to \infty} = \infty \}$

  • $\omega (g(n)) = \{f(n) | \exists n_0> 0 s.t. \forall c>0 and \forall n\geq n_0, f(n) < cg(n)\}$