[코드트리 조별과제] - 점근적 표기법

점근적 표기법

- 의미 : 어떤 함수의 증가 양상을 다른 함수와의 비교로 해석하는 방법. 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중할 수 있는데 이것을 점근적 표기법(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