문제
다음 중 시간 복잡도 O(1)에 대한 설명으로 가장 알맞은 것은?
① 입력 데이터 크기에 관계없이 일정한 횟수의 연산이 수행된다. ② 입력 데이터 크기에 비례하여 연산 횟수가 증가한다. ③ 입력 데이터 크기의 제곱에 비례하여 연산 횟수가 증가한다. ④ 입력 데이터 크기에 따라 연산 횟수가 로그 형태로 증가한다.
정답
1번
해설
정답: 1. O(1)은 입력 크기에 관계없이 항상 일정한 시간 또는 연산 횟수를 갖는 상수 시간 복잡도이다.
오답 풀이
- 1번: O(1)에 부합하는 설명이다.
- 2번: 입력 크기에 비례하는 것은 O(n)이다.
- 3번: 입력 크기의 제곱에 비례하는 것은 O(n²)이다.
- 4번: 로그적으로 증가하는 것은 O(log n)이다.
보충 개념 배열의 인덱스 접근처럼 입력 크기와 무관하게 한 번에 처리되는 연산은 O(1)에 해당한다.