다음 C 코드로 표현한 알고리즘의 시간 복잡도는?Algorithm(in… | [7급 국가직 자료구조론] 25년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 25년 1회차

다음 C 코드로 표현한 알고리즘의 시간 복잡도는?Algorithm(int n) {
    int i, j, k;
    int sum = 0;
    for(i = 0; i < 1000; i++)
        for(j = 1; j < (n - 500); j++)
            for(k = (n - 100); k < (n + 100); k++)
                sum = sum + i + j + k;
}

 $O(1)$

 $O(n)$

 $O(n^2)$

 $O(n^3)$

해설

바깥 루프는 1000회, 가장 안쪽 루프는 200회로 고정되고 n에 비례하는 것은 가운데 루프뿐이므로  $O(n)$ 이다.
반복 횟수: i 루프 1000회 × j 루프  $n-502$ 회(j = 1 ~ n-502) × k 루프 200회
총 연산:  $1000 \times 200 \times (n-502)$ 
상수 계수를 버리면 선형 시간이다.
 $O(1)$ : j 루프 횟수가 n에 따라 늘어나므로 상수 시간이 아니다.
 $O(n^2)$ : k 루프는  $n-100$ 부터  $n+100$  직전까지로 폭이 200으로 고정되어 n에 비례하지 않는다.
 $O(n^3)$ : i 루프도 1000회 고정이라 n에 의존하는 루프는 하나뿐이다.

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

이어서 풀어보기

[7급 국가직 자료구조론] 25년 1회차 25문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요

비슷한 기출

7급 국가직 자료구조론 기출문제 암기장 전체 보기

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→