한양과학기술고등학교

에듀테크 프로젝트 대시보드

Big-O 표기법

입력이 커지면 코드는 얼마나 느려질까?

Big-O는 "정확히 몇 초"가 아니라 입력 크기 n이 커질 때 연산 횟수가 어떤 모양으로 늘어나는지를 나타낸다. 상수와 낮은 차수 항은 버리고 가장 빠르게 자라는 항만 남긴다. 아래 슬라이더로 n을 키우면서 각 복잡도가 얼마나 벌어지는지 직접 확인해 보자.

16

막대는 같은 n에서의 연산 횟수를 로그 스케일로 그린 것이다. 한 칸 = 약 10배.

O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(2ⁿ)

성장 곡선 — n이 1부터 64까지 늘어날 때 (세로축: 로그 스케일)

O(1) 상수

입력이 아무리 커져도 연산 횟수가 그대로. 가장 이상적.

배열 인덱스 접근, 해시맵 조회, 스택 push/pop

O(log n) 로그

한 단계마다 후보를 절반으로 줄인다. n이 10억이어도 약 30번.

이진 탐색, 균형 BST 탐색, 힙 삽입

O(n) 선형

모든 원소를 한 번씩. 입력이 2배면 시간도 2배.

배열 순회, 최댓값 찾기, 선형 탐색

O(n log n) 선형로그

비교 기반 정렬의 한계선. 실무에서 "빠른 정렬"의 기준.

병합 정렬, 퀵 정렬(평균), 힙 정렬

O(n²) 제곱

이중 반복문. n이 1,000이면 100만 번 — 슬슬 위험.

버블/선택 정렬, 모든 쌍 비교, 2중 for문

O(2ⁿ) 지수

n이 1 늘 때마다 2배. n=40이면 1조 번. 사실상 실행 불가.

부분집합 전부 나열, 재귀 피보나치(메모 없이)
# O(1) — 몇 개가 들어오든 한 번의 접근 def first(items): return items[0] # O(n) — 원소마다 한 번씩 def total(items): s = 0 for x in items: # n번 반복 s += x return s # O(n^2) — 반복문 안의 반복문 def has_dup(items): for i in range(len(items)): # n번 for j in range(i+1, len(items)): # 다시 n번 → n*n if items[i] == items[j]: return True return False # O(log n) — 매번 탐색 범위를 절반으로 def bsearch(sorted_items, target): lo, hi = 0, len(sorted_items) - 1 while lo <= hi: mid = (lo + hi) // 2 if sorted_items[mid] == target: return mid if sorted_items[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1

왜 상수를 버릴까? 5n + 100 과 n 은 n이 충분히 커지면 같은 비율로 자란다. Big-O는 "규모가 커졌을 때의 경향"만 보므로 O(5n + 100) = O(n) 이다. 또 n² + n 에서는 n² 이 훨씬 빠르게 커지므로 O(n²) 로 쓴다. 단, 상수가 중요한 실무 상황(작은 n, 캐시 효율)도 있으니 Big-O가 전부는 아니다.

💡 O(1)이 항상 O(n)보다 빠른가?

아니다. Big-O는 n이 무한히 커질 때의 이야기다. 예를 들어 "항상 1억 번 연산하는 O(1)"과 "n번 연산하는 O(n)"이 있으면, n이 100일 때는 O(n) 쪽이 압도적으로 빠르다. Big-O는 확장성(scalability)의 지표이지, 특정 입력에서의 절대 속도 보장이 아니다.

💡 Big-O, Big-Ω, Big-Θ 차이

O(빅오)는 상한 — "아무리 나빠도 이보다 빠르다". Ω(빅오메가)는 하한 — "아무리 좋아도 이보다 느리다". Θ(빅세타)는 상한과 하한이 같을 때 — "딱 이만큼 자란다". 보통 대화에서 "이 알고리즘은 O(n log n)"이라 하면 사실상 Θ를 뜻하는 경우가 많다.

💡 시간 복잡도 말고 공간 복잡도도 있다

공간 복잡도는 추가로 사용하는 메모리가 n에 따라 어떻게 늘어나는지를 뜻한다. 제자리(in-place) 정렬은 O(1) 추가 공간, 병합 정렬은 O(n) 추가 배열이 필요하다. 재귀 함수는 호출 스택도 공간을 쓰므로, 깊이가 n이면 O(n) 공간을 잡아먹는다.