[알고리즘 분석]9. Relatives of Big-Oh(빅 오와 유사한 방법들)

목차

1. big-Omega, big-Theta

2. 각각의 특징

 

1. big-Omega, big-Theta

1) big-Omega

- f(n)이 Ω(g(n))과 같기 위해서는 양의 정수 c와 n0가 f(n) >= cg(n), n >= n0을 만족해야 합니다.

 

2) big-Theta

- f(n)이 Θ(g(n))과 같기 위해서는 양의 정수 c와 n0가 c'g(n) <= f(n) <= c''g(n), n >= n0을 만족해야 합니다.

 

2. 각각의 특징

1) Big-Oh

- Big-Oh는 f(n)이 O(g(n))에 비해 증가율이 작거나 같다.

 

2) big-Omega

- big-Omega는 f(n)이 Ω(g(n))에 비해 증가율이 크거나 같다.

 

3) big-Theta

- big-Theta는 f(n)이 Θ(g(n))에 비해 증가율이 같다.