문제
빅 오(O) 표기법 중, O(1)에 대한 설명으로 옳은 것은?
① 항상 일정한 수행 횟수를 가지는 시간 복잡도이다. ② 항상 한 번의 수행 횟수를 가지는 시간 복잡도이다. ③ 연산 횟수가 일정하게 증가하는 시간 복잡도이다. ④ 연산 횟수가 늘어나는 폭이 점점 커지는 시간 복잡도이다.
정답
1번
해설
정답: 1. O(1)은 입력 크기와 관계없이 일정한 수행 횟수를 가지는 시간 복잡도이다.
오답 풀이
- 1번: 입력 크기와 무관하게 일정한 시간이 걸리는 경우이다.
- 2번: 반드시 한 번만 수행된다는 의미는 아니다.
- 3번: 연산 횟수가 입력에 비례해 증가하면 O(n)에 가깝다.
- 4번: 증가 폭이 커지는 경우는 O(n²), O(2^n) 등에 가깝다.
보충 개념 O(1)은 상수 시간 복잡도이며 배열 인덱스 접근 등이 대표적이다.