다음 알고리즘의 시간 복잡도를 빅세타(\Theta) 표기법으로 표현한 … | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 16년 1회차
다음 알고리즘의 시간 복잡도를 빅세타() 표기법으로 표현한 것은? (단, n > 0)int iterate(int n)
{
int i, count = 0;
for (i = 1; i < n; i *= 2)
count++;
return count;
}
1
2
3
4
해설
시간 복잡도는 이다.
i는 1, 2, 4, 8, …처럼 매 반복 2배로 커지고 i < n 동안만 반복하므로, 반복 횟수는 이 되는 최소 k, 즉 이다.
- 은 i가 1씩 증가할 때의 반복 횟수이다.
- 은 로그 반복 루프를 바깥 루프가 n번 감쌀 때의 복잡도이며, 이 함수에는 바깥 루프가 없다.
- 은 선형 루프 두 개가 중첩될 때의 복잡도이다.
오류나 개정된 내용이 보이면 알려주세요