다음 알고리즘의 시간 복잡도를 빅오(O) 표기법으로 표현한 것으로 옳은… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 15년 1회차
다음 알고리즘의 시간 복잡도를 빅오(O) 표기법으로 표현한 것으로 옳은 것은?Procedure calculate(int n)
{
int i, k, m, x = 0;
for (i = 0; i < (n - 5); i++)
for (k = 0; k < 100; k++)
for (m = 0; m < 1000; m++)
x++;
}
1
O(logn)
2
O(n)
3
O(n2)
4
O(n3)
해설
시간 복잡도는 이다.
바깥 루프는 n−5회 돌고, 안쪽 두 루프는 n과 무관하게 100×1000회를 상수로 반복한다. 총 실행 횟수 에서 상수를 제거하면 n에 선형 비례한다.
- : 반복 변수가 배수로 늘거나 줄지 않으므로 로그 복잡도가 아니다.
- : 안쪽 루프의 반복 횟수는 n이 아니라 고정값이다.
- : 3중 루프이지만 n에 의존하는 루프는 바깥 하나뿐이다.
오류나 개정된 내용이 보이면 알려주세요