시간 복잡도 함수에 대한 점근 표기법으로 옳은 것만을 모두 고르면?ㄱ.… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 19년 1회차
시간 복잡도 함수에 대한 점근 표기법으로 옳은 것만을 모두 고르면?
ㄱ. n2n+6⋅2n=O(n2n)n^{2n} + 6 \cdot 2^{n} = \boldsymbol{O}(n^{2n})
ㄴ. n2/log⁡n=Θ(n2)n^{2}/\log n = \boldsymbol{\Theta}(n^{2})
ㄷ. n32n+6n23n=O(n22n)n^{3}2^{n} + 6n^{2}3^{n} = \boldsymbol{O}(n^{2}2^{n})
ㄹ. 6n3+log⁡n=O(n3)6n^{3} + \log n = \boldsymbol{O}(n^{3})
1
ㄱ, ㄷ
2
ㄱ, ㄹ
3
ㄴ, ㄷ
4
ㄴ, ㄹ
해설

옳은 것은 ㄱ, ㄹ이다.

빅오는 함수가 상한 함수의 상수배 이하로 자라면 성립하고, 세타는 위아래 모두 같은 차수로 묶여야 성립한다.

  • ㄱ: n2nn^{2n}이 2n2^{n}보다 훨씬 빠르게 증가하므로 전체가 O(n2n)O(n^{2n})이다.
  • ㄹ: 최고차 항이 6n36n^{3}이므로 O(n3)O(n^{3})이다.
  • ㄴ: n2/log⁡nn^{2}/\log n은 n2n^{2}보다 로그 배만큼 작아 하한을 만족하지 못하므로 Θ(n2)\Theta(n^{2})가 아니다.
  • ㄷ: 6n23n6n^{2}3^{n}은 n22nn^{2}2^{n}보다 (3/2)n(3/2)^{n}배로 커지고 첫 항 n32nn^{3}2^{n}도 이미 상한을 넘으므로 O(n22n)O(n^{2}2^{n})이 아니다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 19년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기