다음은 C 언어로 작성된 프로그램의 일부이다. 이 프로그램의 시간 복잡… | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 08년 1회차
다음은 C 언어로 작성된 프로그램의 일부이다. 이 프로그램의 시간 복잡도는?for (i = 1; i < n; i++) {
m = 1;
while (m < i) m = m * 2;
}1
2
3
4
해설
이 프로그램의 시간 복잡도는 이다.
안쪽 while은 m을 2배씩 키우므로 i마다 약 회 반복하고, 바깥 for는 n-1회 돈다.
- : 안쪽 반복 횟수가 i에 비례해 늘어날 때의 값이다.
- : 바깥 반복 n회를 빠뜨린 값이다.
- : 안쪽 반복이 상수 횟수일 때의 값이다.
오류나 개정된 내용이 보이면 알려주세요