알고리즘의 복잡도와 O-Notation의 개념, 유형 및 유형별 연산시간의 차이
정보관리기술사 제134회 3교시 23번 문항으로, 과목은 SW공학/프로젝트관리입니다. ‘시간 복잡도’ 키워드는 정보관리기술사 기출 4문항에 나왔습니다.
원문 문제
정보관리기술사 제134회 23번. 알고리즘의 복잡도와 O-Notation의 개념, 유형 및 유형별 연산시간의 차이
핵심 키워드
- O-Notation
- 시간 복잡도
- 공간 복잡도
- 점근 표기법
- 연산 시간 비교
- 알고리즘 효율성
고득점 가이드 — 1. 개요
알고리즘 복잡도는 입력 크기 n의 변화에 따른 실행 시간(시간 복잡도)과 메모리 사용량(공간 복잡도)을 정량적으로 분석하는 척도이다. O-Notation(Big-O)은 입력이 무한히 커질 때의 상한을 표현하는 점근 표기법으로, 충분히 큰 n에 대해 T(n) ≤ c·f(n)을 만족하는 f(n)을 사용해 알고리즘 효율성을 하드웨어·언어 독립적으로 비교할 수 있게 한다.
출제 이력
- O-Notation기출 1문항
- 시간 복잡도기출 4문항
- 공간 복잡도기출 4문항
- 점근 표기법기출 1문항
- 연산 시간 비교기출 1문항
- 알고리즘 효율성기출 1문항