점근적 표기법
- 의미 : 어떤 함수의 증가 양상을 다른 함수와의 비교로 해석하는 방법. 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중할 수 있는데 이것을 점근적 표기법(Asymptotic notaion)이라 부름. 점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미.
사용 : 함수가 복잡할수록 어느 알고리즘이 효율적인지 비교하는 것이 어려워지기 때문에 함수를 단순화하기 위해 점근 표기법을 사용.
- 종류 : 크게 O(빅-오), Ω(빅-오메가), Θ(빅-세타)가 있음.
O(빅-오)
O는 가장 높은 차수 보다 같거나 높은 식(상한 표기법)
(n)=n3+n2+n−1,g(n)=n5 이었다면, f(n)=O(g(n)) 으로도 나타내 볼 수 있음.
-> f(n)의 차수가 g(n)의 차수보다 같거나 작다는 의미
Ω(빅-오메가)
Ω는 가장 높은 차수 보다 같거나 낮은 식(하한 표기법)
f(n)=n3+n2+n−1,g(n)=n 이었다면, f(n)=Ω(g(n)) 으로도 나타내 볼 수 있음.
->
f(n)의 차수가 g(n)의 차수보다 같거나 크다는 의미
Θ(빅-세타)
Θ는 최고차항(가장 높은 차수) 의미.
n3+n2+n−1에서 가장 높은 차수는 n3 이므로 Θ(n3)
점근적 표기법은 n이 무한히 커졌을 때의 상황에 관심이 있기 때문에 식 앞에 있는 상수값은 항상 무시.
즉, O(9n3−2)=O(n3)이며, 9n3+n2+n−1 식은 O(n3)로 나타낼 수 있음
문제
두 함수 f(x),g(x)가 있습니다.
두 함수의 관계를 점근적 표기법을 통해 표현하려고 할 때, 다음 중 옳은 것은?
(1) f(x)=x^8, g(x)=x^4
(2) f(x)=x^2−1, g(x)=x^2+x+1
해설 :
1번 문제)
f(x)에서 가장 높은 차수를 가진 것은 x^8임. 빅오를 쓰려면 x^8보다 차수가 같거나 높아야함. 하지만 g(x)에서 가장 높은 차수를 가진 것은 x^4. 이 경우는 차수가 작으므로 빅 오메가를 쓰는 것이 가능.
f(x) =O(g(x)) -> 불가능!
f(x) = Ω(g(x)) -> 가능!
f(x) = Θ(g(x)) -> 불가능!
2번 문제)
f(x)에서 가장 높은 차수를 가진 것은 x^2. g(x)에서 가장 높은 차수를 가진것도 x^2. 빅오는 크거나 같은 경우, 빅오메가는 작거나 같은 경우, 빅세타는 최고차항이 같은 경우이므로 전부 가능.
f(x) =O(g(x)) -> 가능!
f(x) = Ω(g(x)) -> 가능!
f(x) = Θ(g(x)) -> 가능!
https://www.codetree.ai/missions/6/problems/translate-notation?&utm_source=clipboard&utm_medium=text