<보기>의 알고리즘 시간 복잡도로 가장 옳은 것은?Algor… | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 자료구조론] 26년 1회차
<보기>의 알고리즘 시간 복잡도로 가장 옳은 것은?Algorithm(int n) {
int i, j, k, l;
int sum = 0;
for (i = 0; i < 500; i++)
for (j = 0; j < 100; j++)
for (k = 1; k < n; k = k * 2)
for (l = 0; l < 10; l++)
sum = sum + i + j + k + l;
}1
2
3
4
해설
시간 복잡도는 이다.
i(500회)·j(100회)·l(10회) 반복은 n과 무관한 상수이고, k는 1부터 2배씩 증가하므로 약 회 반복한다.
총 실행 횟수는 이고, 상수를 제거하면 이다.
- : k 반복 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
- : k가 1씩이 아니라 2배씩 증가하므로 선형이 아니다.
- : n에 의존하는 반복은 하나뿐이고 그마저 로그 횟수이다.
오류나 개정된 내용이 보이면 알려주세요