시간 복잡도 함수에 대한 점근 표기법으로 옳은 것만을 모두 고르면?ㄱ.… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 19년 1회차
시간 복잡도 함수에 대한 점근 표기법으로 옳은 것만을 모두 고르면?ㄱ.
ㄴ.
ㄷ.
ㄹ.
1
ㄱ, ㄷ
2
ㄱ, ㄹ
3
ㄴ, ㄷ
4
ㄴ, ㄹ
해설
옳은 것은 ㄱ, ㄹ이다.
빅오는 함수가 상한 함수의 상수배 이하로 자라면 성립하고, 세타는 위아래 모두 같은 차수로 묶여야 성립한다.
- ㄱ: 이 보다 훨씬 빠르게 증가하므로 전체가 이다.
- ㄹ: 최고차 항이 이므로 이다.
- ㄴ: 은 보다 로그 배만큼 작아 하한을 만족하지 못하므로 가 아니다.
- ㄷ: 은 보다 배로 커지고 첫 항 도 이미 상한을 넘으므로 이 아니다.
오류나 개정된 내용이 보이면 알려주세요