다음 C 코드로 표현한 알고리즘의 시간 복잡도는? for(i=1; i =0; j--) { if(arr[j]>MaxData) arr[j+1]=arr[j]; else break; } arr[j+1]=MaxData; }

오픈채팅

이용권 구매

활용 가이드

앱 설치

버그 신고

개선 요청

다크모드

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

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

다음 C 코드로 표현한 알고리즘의 시간 복잡도는?
for(i=1; i<n; i++) {
    MaxData=arr[i];
    for(j=i-1; j>=0; j--) {
        if(arr[j]>MaxData)
            arr[j+1]=arr[j];
        else
            break;
    }
    arr[j+1]=MaxData;
}

O( $\log n$ )

O( $n\log n$ )

O( $n^2$ )

O( $n^3$ )

해설

주어진 코드는 삽입 정렬이며 시간 복잡도는  $O(n^2)$ 이다.
바깥 반복은 n-1회이고, 안쪽 반복은 MaxData보다 큰 원소를 한 칸씩 뒤로 미는 동안 최대 i회 수행된다. 역순 입력(최악)에서는  $1+2+\cdots+(n-1) = \dfrac{n(n-1)}{2}$ 회 비교·이동한다.
 $O(\log n)$ 은 탐색 범위를 절반씩 줄이는 이진 탐색 수준으로, 모든 원소를 다뤄야 하는 정렬에는 불가능하다.
 $O(n\log n)$ 은 병합·힙 정렬 같은 분할 기반 정렬의 복잡도로, 원소를 한 칸씩 옮기는 이 코드의 최악보다 작다.
 $O(n^3)$ 은 3중 반복에 해당하며, 이 코드는 2중 반복이다.

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

이어서 풀어보기

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

비슷한 기출

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

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

→