다음 알고리즘의 시간 복잡도를 빅세타(\Theta) 표기법으로 표현한 … | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 16년 1회차
다음 알고리즘의 시간 복잡도를 빅세타(Θ\Theta) 표기법으로 표현한 것은? (단, n > 0)
int iterate(int n)
{
int i, count = 0;
for (i = 1; i < n; i *= 2)
count++;
return count;
}
1
Θ(log⁡n)\Theta(\log n)
2
Θ(n)\Theta(n)
3
Θ(nlog⁡n)\Theta(n \log n)
4
Θ(n2)\Theta(n^2)
해설

시간 복잡도는 Θ(log⁡n)\Theta(\log n)이다.

i는 1, 2, 4, 8, …처럼 매 반복 2배로 커지고 i < n 동안만 반복하므로, 반복 횟수는 2k≥n2^k \ge n이 되는 최소 k, 즉 ⌈log⁡2n⌉\lceil \log_2 n \rceil이다.

  • Θ(n)\Theta(n)은 i가 1씩 증가할 때의 반복 횟수이다.
  • Θ(nlog⁡n)\Theta(n \log n)은 로그 반복 루프를 바깥 루프가 n번 감쌀 때의 복잡도이며, 이 함수에는 바깥 루프가 없다.
  • Θ(n2)\Theta(n^2)은 선형 루프 두 개가 중첩될 때의 복잡도이다.

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

이어서 풀어보기

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