35. 알고리즘 시간 복잡도 O(1)이 의미하는 것은?

[정보처리기사 기출 해설] 알고리즘 시간 복잡도 – O(1)의 의미 (2020년 1회)

📌 출처: 2020년 정보처리기사 필기 1회차
📖 과목: 소프트웨어 개발

---

❓ 기출문제 원문

35. 알고리즘 시간 복잡도 O(1)이 의미하는 것은?

① 컴퓨터 처리가 불가
② 알고리즘 입력 데이터 수가 한 개
③ 알고리즘 수행 시간이 입력 데이터 수와 관계없이 일정
④ 알고리즘 길이가 입력 데이터보다 작음

---

✅ 정답: ③ 알고리즘 수행 시간이 입력 데이터 수와 관계없이 일정

---

📘 개념 설명: 시간 복잡도(Time Complexity)

시간 복잡도란, 알고리즘이 입력 데이터를 처리하는 데 걸리는 시간과 **입력 크기(n)**의 관계를 표현한 것입니다.
이는 알고리즘의 효율성을 비교하는 데 사용되며, 빅오(Big-O) 표기법으로 표현됩니다.

주요 시간 복잡도 종류

• O(1): 입력 크기와 무관하게 항상 일정한 시간
• O(log n): 로그 시간 (이진 탐색 등)
• O(n): 선형 시간 (for문 1회 반복 등)
• O(n²): 이중 루프 등
• O(2ⁿ): 지수 시간 (브루트포스 완전탐색 등)

---

🔍 정답 해설

**O(1)**은 입력 크기와 관계없이 항상 일정한 횟수로 실행되는 알고리즘을 의미합니다.

예를 들어:

python

def get_first_element(lst): return lst[0]

• 위 함수는 리스트의 크기가 10이든 1,000,000이든 무조건 한 번만 동작합니다.
• → 따라서 수행 시간이 입력 크기에 영향을 받지 않고 일정합니다.

✅ 따라서 정답은 ③ 알고리즘 수행 시간이 입력 데이터 수와 관계없이 일정입니다.

---

❌ 보기별 오답 해설

• ① 컴퓨터 처리가 불가
  → 시간 복잡도는 수행 불가능 여부가 아닌, 시간 효율성을 나타냅니다.
• ② 입력 데이터 수가 한 개
  → 입력 크기와 무관하게 동작하는 것이 핵심이지, 입력이 한 개라는 조건과는 다릅니다.
• ④ 알고리즘 길이가 입력 데이터보다 작음
  → 알고리즘의 길이와 입력 크기의 비교는 시간 복잡도와 직접적인 관계가 없습니다.

---

🎯 핵심 요약

• **O(1)**은 "상수 시간"이라 불리며, 입력 크기와 상관없이 일정한 시간에 실행되는 알고리즘입니다.
• 이는 가장 이상적인 시간 복잡도 형태 중 하나입니다.

---

📎 참고자료

• 『시나공 정보처리기사 필기 기출문제집 (2020년 1회)』
• 알고리즘 이론 및 빅오 표기법 요약
• 한국산업인력공단 정보처리기사 시험 문제지