<보기>의 알고리즘 시간 복잡도로 가장 옳은 것은?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
O(1)O(1)
2
O(n)O(n)
3
O(n2)O(n^2)
4
O(log⁡n)O(\log n)
해설

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

i(500회)·j(100회)·l(10회) 반복은 n과 무관한 상수이고, k는 1부터 2배씩 증가하므로 약 log⁡2n\log_2 n회 반복한다.

총 실행 횟수는 500×100×10×log⁡2n500 \times 100 \times 10 \times \log_2 n이고, 상수를 제거하면 O(log⁡n)O(\log n)이다.

  • O(1)O(1): k 반복 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
  • O(n)O(n): k가 1씩이 아니라 2배씩 증가하므로 선형이 아니다.
  • O(n2)O(n^2): n에 의존하는 반복은 하나뿐이고 그마저 로그 횟수이다.

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

이어서 풀어보기

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