Ch.1 빅오와 복잡도 분석
Big-O 표기법 — 알고리즘의 성적표
이 코드가 얼마나 빠를까?
선배가 코드 리뷰에서 '이거 O(n²)인데, O(n)으로 바꿔'라고 했습니다. 이 말이 무슨 뜻인지 정확히 이해해봅시다.
같은 for 루프인데 왜 복잡도가 다를까?
Big-O는 '최악의 경우 연산 횟수가 n에 비례해서 어떻게 증가하는가'를 한마디로 표현합니다.
핵심 개념
Big-O
최악의 경우 연산 횟수의 증가 차수를 나타내는 표기법
상수 무시
Big-O는 계수와 낮은 차수 항을 무시한다
핵심 내용
Big-O는 알고리즘의 성적표입니다
시험에서 점수가 아니라 등급을 매기듯, 알고리즘도 등급이 있습니다
Big-O 규칙 3가지: 1. 상수는 무시 — O(3n) → O(n) 2. 낮은 차수 무시 — O(n² + n) → O(n²) 3. 최악의 경우 기준으로 측정
데이터가 아무리 많아도 딱 한 번만 실행
# O(1) — 상수 시간
def get_first(arr):
return arr[0] # 항상 1번 연산
# 배열이 10개든 10억 개든 동일배열 인덱싱, 딕셔너리 조회, 해시맵 접근 — 모두 O(1)
데이터가 n개면 연산도 n번
# O(n) — 선형 시간
def find_max(arr):
max_val = arr[0]
for x in arr: # n번 반복
if x > max_val:
max_val = x
return max_valfor 루프가 하나 → 대부분 O(n)
for 루프 안에 for 루프가 있으면 n × n = n²
# O(n²) — 이차 시간
def bubble_sort(arr):
n = len(arr)
for i in range(n): # n번
for j in range(n - 1): # n번
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]루프 카운팅 규칙: for 1개 → O(n) for 중첩 2개 → O(n²) for 중첩 3개 → O(n³)
면접에서 O(n²)이 나오면 반드시 '더 나은 방법이 있을까?'라고 자문하세요
흔히 쓰는 Big-O를 한눈에 비교합니다
O(5n + 3)을 Big-O로 단순화하면?
for 루프가 2개 중첩되어 있으면 시간 복잡도는?
배열의 첫 번째 원소에 접근하는 arr[0]의 시간 복잡도는?
arr[0]은 O(1)이다
Big-O 마스터
핵심 용어
Big-O
최악의 경우 연산 횟수의 증가 차수를 나타내는 표기법
상수 무시
Big-O는 계수와 낮은 차수 항을 무시한다
O(1)
1번 — 즉시
O(log n)
20번 — 매우 빠름
O(n)
100만 번 — 적절
O(n log n)
2,000만 번 — 보통
O(n²)
1조 번 — 위험
정리 노트
Big-O 표기법 — 알고리즘의 성적표
Big-O 규칙
- 상수 무시
- O(3n) → O(n)
- 낮은 차수 무시
- O(n² + n) → O(n²)
- 최악 기준
- 항상 최악의 경우로 측정
루프 카운팅
- for 1개
- O(n)
- for 중첩 2개
- O(n²)
- 인덱스 접근
- O(1)
Big-O는 '최악의 경우, n이 커질 때 얼마나 느려지는가'를 한마디로 표현한다!
시각 자료
핵심 정리
- 1Big-O = 최악의 경우 연산 증가 차수
- 2상수와 낮은 차수 항은 무시
- 3O(1) < O(log n) < O(n) < O(n²)
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작