새소식

코딩테스트

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

  • -

점근적 표기법

- 의미 : 어떤 함수의 증가 양상을 다른 함수와의 비교로 해석하는 방법. 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중할 수 있는데 이것을 점근적 표기법(Asymptotic notaion)이라 부름. 점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미.

사용 : 함수가 복잡할수록 어느 알고리즘이 효율적인지 비교하는 것이 어려워지기 때문에 함수를 단순화하기 위해 점근 표기법을 사용.

- 종류 : 크게 , , 빅-세타)가 있음.

 

O(빅-오)

는 가장 높은 차수 보다 같거나 높은 식(상한 표기법)

 이었다면,  으로도 나타내 볼 수 있음.

-> f(n)의 차수가 g(n)의 차수보다 같거나 작다는 의미

 

Ω(빅-오메가)

는 가장 높은 차수 보다 같거나 낮은 식(하한 표기법)

 이었다면,  으로도 나타내 볼 수 있음.

->

f(n)의 차수가 g(n)의 차수보다 같거나 크다는 의미

 

빅-세타)

는 최고차항(가장 높은 차수) 의미.
에서 가장 높은 차수는  이므로 

 

점근적 표기법은 n이 무한히 커졌을 때의 상황에 관심이 있기 때문에 식 앞에 있는 상수값은 항상 무시. 

즉,   식은 로 나타낼 수 있음

 

 

문제

두 함수 가 있습니다.
두 함수의 관계를 점근적 표기법을 통해 표현하려고 할 때, 다음 중 옳은 것은?

(1) , 

(2) , 

 

해설 :

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

Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.