공개 기출자동 검사 완료2024년 지방직 기출 · 컴퓨터일반 · 프로그래밍 · 18번

다음 C 언어로 작성된 코드의 시간 복잡도는? (단, n은 임의의 양의 정수이다)

ITPASSLAB 재구성 문제 자료

1
Θ(n)
정답 근거바깥 반복문은 n회, 안쪽 반복문은 고정된 500회 실행됩니다. 상수 500을 제거하면 전체 시간 복잡도는 Θ(n)입니다.
2
Θ(n²)
오답 이유안쪽 반복 횟수가 n이 아니라 500으로 고정되어 있으므로 Θ(n²)이 아닙니다.
3
Θ(log n)
오답 이유반복 변수가 매회 절반으로 줄어드는 구조가 아니므로 Θ(log n)이 아닙니다.
4
Θ(n log n)
오답 이유정렬처럼 n개 원소마다 로그 단계가 필요한 구조가 아니므로 Θ(n log n)이 아닙니다.

정답·상세해설

정답 1번

첫 번째 반복문은 입력 크기 n에 비례해 실행됩니다. 두 번째 반복문은 500회로 고정되어 상수 시간이고, printf의 곱셈도 상수 시간입니다. 따라서 전체 시간복잡도는 Θ(n)입니다.

콘텐츠 기록