Dazzling 개발 노트
[코드트리] 점근적 표기법 본문
본래 점근적 표기법은 수학적인 개념이기 때문에 엄밀한 정의를 설명하기엔 수학적 지식이 약간 필요하지만, 우리는 간단하게 개념을 이해할 수 있는 수준으로 설명하도록 하겠습니다.
점근적 표기법에는 크게 , , 가 있습니다. 각각 빅-오, 빅-오메가, 빅-세타라고 부릅니다.
간단한 다항식 이라는 식이 있다고 가정하겠습니다.
- 는 가장 높은 차수 보다 같거나 높은 식을 뜻합니다. 즉, 에서 가장 높은 차수는 이므로 , , 모두 맞는 말이지만, 우리는 앞으로 이 식을 보게 되었을 때 좀 tight하게 라고 부르게 될 것이며, 이것이 바로 시간복잡도를 재는 척도로 쓰이게 됩니다.
- 이때 표현은 와 같이 나타낼 수 있습니다.
만약 이었다면, 으로도 나타내 볼 수 있습니다. 이는 f(n)의 차수가 g(n)의 차수보다 같거나 작다는 의미를 갖습니다. - 는 가장 높은 차수 보다 같거나 낮은 식을 뜻합니다.
즉, 에서 가장 높은 차수는 이므로 , , 모두 맞는 말이 됩니다. - 만약 이었다면, 으로도 나타내 볼 수 있습니다. 이는 f(n)의 차수가 g(n)의 차수보다 같거나 크다는 의미를 갖습니다.
- 는 최고차항(가장 높은 차수)을 뜻합니다.
즉, 에서 가장 높은 차수는 이므로 이 됩니다.
또, 점근적 표기법은 n이 무한히 커졌을 때의 상황에 관심이 있기 때문에 식 앞에 있는 상수값은 항상 무시합니다. 즉, 을 만족하며, 이 말은 즉 식은 로 나타낼 수 있음을 뜻합니다. Ω, Θ 역시 마찬가지로 상수값을 전부 무시하게 됩니다.
Side Note
은 참일까요?
정답은 참입니다. n이 커짐에 따라 값이 훨씬 커지게 되기 때문에, 모든 지수승으로 이루어져 있는 식은 전부 다항식보다 크다고 할 수 있습니다.
[기호 변환]
문제
https://www.codetree.ai/missions/6/problems/translate-notation?&utm_source=clipboard&utm_medium=text
두 함수 가 있습니다.
두 함수의 관계를 점근적 표기법을 통해 표현하려고 할 때, 다음 중 옳은 것을 모두 고르세요.
(1) ,
(2) ,
풀이/후기
- O : 가장 높은 차수보다 같거나 높은 식,
- Ω : 가장 높은 차수보다 같거나 낮은 식,
- θ : 최고차항
1 - 가장 높은 차수보다 크거나 같다
2 - 가장 높은 차수보다 작거나 같다
3 - 최고차항(가장 높은 차수)
4 - 차수가 2로 같다
5 - 차수가 2로 같다
6 - 차수가 2로 같다
[O, Ω, Θ]
문제
우리는 연산 횟수를 일일히 구하는 수고를 덜기 위해, 수학에서 사용하는 점근적 표기법이라는 방법을 사용해 시간복잡도를 표현 하려고 합니다.
다음 함수를 점근적 표기법을 통해 표현해보려고 합니다.
댜음 중 옳은 것을 골라주세요.
풀이/후기
- O : 가장 높은 차수보다 같거나 높은 식,
- Ω : 가장 높은 차수보다 같거나 낮은 식,
- θ : 최고차항
[펜트하우스]
문제
https://www.codetree.ai/missions/6/problems/penthouse?&utm_source=clipboard&utm_medium=text
펜트하우스에 코드들이 입주를 합니다. 모두가 높은 층에 입주하고 싶겠지만, 자리는 한정되어 있기 때문에 다음과 같은 규칙으로 배정하기로 했습니다.
두 코드의 시간복잡도를 각각 이라고 할 때,
- 이 성립하면, 두 코드는 같은 층에 배정됩니다.
- 만약 이지만 이라면, 은 보다 낮은 층에 배정됩니다.
다음과 같은 8개의 코드의 시간복잡도가 있다고 합시다. 이 경우 최상층으로 가는 코드의 수와 그 아래층으로 가는 코드의 수를 합치면 어떻게 될까요?
풀이/후기
- O : 가장 높은 차수보다 같거나 높은 식,
- Ω : 가장 높은 차수보다 같거나 낮은 식,
- θ : 최고차항
1/2n^5
2^n, logn, nlogn, n^2logn
n^3, 10n^3
최상층 1개, 아래층 2개 총 3개
[수식들의 관계]
문제
https://www.codetree.ai/missions/6/problems/time-complexity?&utm_source=clipboard&utm_medium=text
다음은 O, Ω, Θ 기호를 활용한 식에 대한 설명입니다.
옳은 것을 모두 고르세요.
풀이/후기
- O : 가장 높은 차수보다 같거나 높은 식,
- Ω : 가장 높은 차수보다 같거나 낮은 식,
- θ : 최고차항
참고
