서론
- 시간복잡도에 사용되는 점근적 표기법에 대해 공부한 내용을 정리하였습니다.
내용 정리
- 코드트리에선 O, Ω, Θ에 대해 간략하게 설명하고 있습니다.
1.O(빅-오)
- 가장 높은 차수와 같거나 높은 식을 나타냅니다.
- f(x)와 g(x)가 있을 때, f(x) = O(g(x))가 성립한다면 g(x)는 f(x)의 최고차항과 같거나 높은 차수의 항을 가지고 있다고 표현합니다.
ex) f(x) = x^2 + x + 1일 때 f(x) = O(g(x))라면
g(x) = x^3 (o), x^2 - 1 (o), x^100 (o)
g(x) = x + 1 (x), log(x) (x) - 알고리즘에 활용할 땐 tight하게 최고차항만을 나타냅니다.
ex) f(x) = x^3 + x^2 + x - 1 -> f(x) = O(x^3)
2.Ω(빅-오메가)
- 가장 높은 차수와 같거나 낮은 식을 나타냅니다.
- f(x)와 g(x)가 있을 때, f(x) = Ω(g(x))라면 g(x)는 f(x)의 최고차항과 같거나 낮은 차수의 최고차항을 가지고 있다고 표현합니다.
ex) f(x) = x^2 - x일 때 f(x) = Ω(g(x))라면
g(x) = x^2 + 3 (o), x + 1 (o), xlog(x) (o)
g(x) = x^3 (x), x^2log(x) - 1 (x)
3.Θ(빅-세타)
- 가장 높은 차수(최고차항)을 나타냅니다.
- f(x)와 g(x)가 있을 때, f(x) = Θ(g(x))라면 g(x)의 최고차항은 f(x)의 최고차항과 같습니다.
ex) f(x) = x^3 + 1 일 때, f(x) = Θ(g(x))라면
g(x) = x^3 - 1 (o), x^3 (o)
g(x) = x^2 - 1 (x), x^4 + x^3 + 1 (x) - 이 때 f(x) = Θ(g(x))가 성립한다면 f(x) = O(g(x))와 f(x) = Ω(g(x)) 도 성립합니다.
여담
- 생각보다 내용이 애매모호해서 이해가 쉽지 않아 블로그에 정리하면서 다시 되새겨보았습니다.
- 이제까진 코드트리를 코딩문제 풀이로만 활용했는데, 알고리즘 공부에도 굉장히 도움이 될 것 같습니다.
코딩공부합니다