시간 복잡도 (Big-O)
입력 크기(N)에 따라 알고리즘의 실행 시간이 어떻게 증가하는지 표현하는 표기법
복잡도 순서 (느린 순)
O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2^N)
빠름 ──────────────────────────────────────── 느림
시각적 비교 (N=16 기준)
O(1) : ■
O(log N) : ■■■■
O(N) : ■■■■■■■■■■■■■■■■
O(N log N) : ■■■■ × 16 = 64
O(N²) : ■ × 256
O(2^N) : ■ × 65536 😱
주요 복잡도 설명
| 복잡도 | 이름 | 예시 | N=100만 |
|---|
| O(1) | 상수 | 배열 인덱스 접근 | 1 |
| O(log N) | 로그 | 이진 탐색 | 20 |
| O(N) | 선형 | 배열 순회 | 100만 |
| O(N log N) | 선형로그 | 정렬 (병합/퀵) | 2000만 |
| O(N²) | 제곱 | 이중 for문 | 1조 💀 |
| O(2^N) | 지수 | 부분집합 | ∞ |
코드로 보는 복잡도
# O(1) - 상수 시간
def get_first(arr):
return arr[0] # 항상 1번
# O(N) - 선형
def find(arr, target):
for item in arr: # N번 반복
if item == target:
return True
# O(N²) - 제곱
def has_duplicate(arr):
for i in range(len(arr)): # N번
for j in range(len(arr)): # × N번
if i != j and arr[i] == arr[j]:
return True
# O(log N) - 로그
def binary_search(arr, target):
lo, hi = 0, len(arr)-1
while lo <= hi: # 매번 절반 제거
mid = (lo+hi)//2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
자료구조별 복잡도
| 연산 | 배열 | 연결리스트 | 해시 | BST |
|---|
| 접근 | O(1) | O(N) | - | O(log N) |
| 검색 | O(N) | O(N) | O(1) | O(log N) |
| 삽입 | O(N) | O(1) | O(1) | O(log N) |
| 삭제 | O(N) | O(1) | O(1) | O(log N) |
정렬 알고리즘 복잡도
| 알고리즘 | 최선 | 평균 | 최악 |
|---|
| 버블 정렬 | O(N) | O(N²) | O(N²) |
| 삽입 정렬 | O(N) | O(N²) | O(N²) |
| 병합 정렬 | O(N log N) | O(N log N) | O(N log N) |
| 퀵 정렬 | O(N log N) | O(N log N) | O(N²) |
실무에서 의미
N = 100만 (백만 건 데이터)
O(N²) → 약 12일 (비실용적)
O(N log N) → 약 20초
O(N) → 약 1초
O(log N) → 약 0.00002초
Big-O 판단 팁
| 패턴 | 복잡도 |
|---|
| 반복 없음 | O(1) |
| 단일 for문 | O(N) |
| 이중 for문 | O(N²) |
| 매번 절반 | O(log N) |
| 정렬 후 처리 | O(N log N) |
| 재귀 2개 분기 | O(2^N) |
Q.Big-O 표기법이 무엇이고 왜 사용하나요?
입력이 커질 때 연산 횟수가 어떤 비율로 늘어나는지를 나타내는 표기입니다. 정확한 횟수가 아니라 성장 속도를 봅니다.
| 표기 | 뜻 | 예 |
|---|
| O(1) | 입력과 무관 | 배열 인덱스 접근 |
| O(log n) | 매 단계에서 절반씩 줄인다 | 이진 탐색 |
| O(n) | 입력에 비례 | 전체 순회 |
| O(n log n) | 정렬의 실질적 하한 | 병합 정렬 |
| O(n의 제곱) | 이중 순회 | 모든 짝 비교 |
상수와 낮은 차수를 버리는 이유는 규모가 커질 때 가장 높은 차수가 결과를 지배하기 때문입니다. 하드웨어나 언어가 바뀌면 상수는 달라지지만 차수는 그대로여서, 구현과 무관하게 알고리즘을 비교할 수 있습니다.
흔한 실수: Big-O를 실행 시간으로 읽는 것. O(n)이 O(n의 제곱)보다 항상 빠른 것이 아니고, n이 작으면 상수가 작은 쪽이 이깁니다. 차수로 후보를 좁히고 실제 측정으로 고르는 것이 맞습니다.
Q.O(N)과 O(N log N)의 차이를 실제 예시로 설명해주세요.
log n 은 아주 완만하게 자라므로 격차가 크지 않습니다. 정렬이 필요한지가 실제 갈림길입니다.
| 원소 수 | O(n) | O(n log n) | 배수 |
|---|
| 1,000 | 1,000 | 약 1만 | 10배 |
| 100만 | 100만 | 약 2,000만 | 20배 |
| 10억 | 10억 | 약 300억 | 30배 |
원소가 100만 배 늘어도 배수는 10배에서 30배로만 벌어집니다. O(n의 제곱)과의 격차(100만 배에서 5만 배)와 비교하면 완만합니다.
실무 예로 보면 이렇습니다.
O(n) 중복 찾기를 해시 집합으로. 메모리를 n만큼 쓴다
O(n log n) 정렬한 뒤 인접 비교. 추가 메모리가 거의 없다
흔한 실수: O(n log n)을 무조건 피하려는 것. 정렬해두면 범위 조회와 이웃 찾기가 함께 싸지므로, 그 뒤 연산까지 보면 총합이 더 나은 경우가 많습니다.
Q.배열과 해시 테이블의 시간 복잡도를 비교해주세요.
찾는 방식이 다릅니다. 배열은 위치를 알아야 하고 해시는 값으로 위치를 계산합니다.
| 연산 | 배열 (미정렬) | 배열 (정렬) | 해시 테이블 |
|---|
| 인덱스로 읽기 | O(1) | O(1) | 해당 없음 |
| 값으로 찾기 | O(n) | O(log n) | 평균 O(1) |
| 삽입 | 끝이면 O(1) | O(n) | 평균 O(1) |
| 삭제 | O(n) | O(n) | 평균 O(1) |
| 정렬된 순회 | 정렬 필요 | O(n) | 불가능 |
| 범위 조회 | 불가능 | O(log n) 이후 순차 | 불가능 |
마지막 두 줄이 선택 기준입니다. 해시는 등가 조회만 빠르고 순서를 모릅니다. 그래서 DB 인덱스는 범위와 정렬이 필요해 B-tree를 씁니다.
흔한 실수: 해시가 항상 빠르다고 답하는 것. 평균이 O(1)이고 충돌이 몰리면 O(n)까지 떨어집니다. 그리고 해시 계산 자체에 상수 비용이 있어 원소가 적으면 배열 순회가 더 빠릅니다.
Q.O(N²) 알고리즘을 개선하는 방법은 무엇이 있나요?
이중 순회가 왜 필요한지를 보고 그 이유를 없앱니다.
| 방법 | 언제 | 결과 |
|---|
| 해시로 조회를 대체 | 안쪽 루프가 "이 값이 있나"를 찾을 때 | O(n) |
| 정렬 후 두 포인터 | 짝을 찾을 때 | O(n log n) |
| 정렬 후 이진 탐색 | 안쪽에서 특정 값을 찾을 때 | O(n log n) |
| 누적 합이나 슬라이딩 윈도 | 구간 합이나 구간 최댓값을 반복 계산할 때 | O(n) |
| 메모이제이션 | 같은 부분 문제를 다시 계산할 때 | 문제에 따라 |
두 수의 합 찾기
O(n의 제곱) 모든 짝을 확인한다
O(n) 지금까지 본 값을 집합에 담고 목표에서 뺀 값이 있는지 본다
흔한 실수: 무조건 차수를 낮추려는 것. n이 수백 이하로 확실하면 이중 순회가 읽기 쉽고 상수도 작아 실제로 더 빠릅니다. 개선은 n이 커질 근거가 있을 때 합니다.
Q.O(n log n)과 O(n²)의 실질적 차이를 예시로 설명해주세요
n 이 커지면 격차가 폭발합니다. 정렬을 예로 들면 이렇습니다.
| 원소 수 | O(n log n) | O(n의 제곱) | 배수 |
|---|
| 1,000 | 약 1만 | 100만 | 100배 |
| 10만 | 약 170만 | 100억 | 6,000배 |
| 100만 | 약 2,000만 | 1조 | 5만배 |
초당 1억 번 연산한다고 보면 100만 건에서 앞은 0.2초, 뒤는 약 3시간입니다. 그래서 데이터가 커질 계획이라면 차수를 먼저 낮춰야 합니다.
흔한 실수: 항상 O(n log n)이 빠르다고 답하는 것. n 이 작으면 상수가 작은 O(n의 제곱)이 이깁니다. 실제 정렬 라이브러리도 원소가 수십 개 이하인 구간은 삽입 정렬로 처리합니다.
Q.공간복잡도와 시간복잡도 트레이드오프 경험이 있나요?
대표적인 것이 캐싱과 메모이제이션입니다. 계산 결과를 저장해 시간을 사고 메모리를 냅니다.
| 예 | 시간 | 공간 |
|---|
| 피보나치를 재귀로 | 지수 | 상수 |
| 메모이제이션을 붙이면 | O(n) | O(n) |
| 중복 조회를 캐시로 | 크게 줄어든다 | 캐시 크기만큼 늘어난다 |
| 정렬 후 이진 탐색 | O(n log n) 후 O(log n) | 추가 공간 없이 가능 |
| 해시 집합으로 중복 확인 | O(n) | O(n) |
반대 방향도 있습니다. 메모리 예산이 100MB 인데 집합이 960MB 를 요구하면, 비트 배열로 12.5MB 로 줄이고 대신 다룰 수 있는 연산을 좁히는 선택을 합니다.
흔한 실수: 항상 시간을 우선하는 것. 서버 메모리는 유한하고, 넘치면 스왑이나 종료로 이어져 시간도 함께 잃습니다.
Q.최선/평균/최악 시간복잡도가 다른 알고리즘 예시는?
퀵 정렬이 가장 유명합니다.
| 알고리즘 | 최선 | 평균 | 최악 | 최악이 되는 조건 |
|---|
| 퀵 정렬 | O(n log n) | O(n log n) | O(n의 제곱) | 피벗이 매번 한쪽 끝 값 |
| 삽입 정렬 | O(n) | O(n의 제곱) | O(n의 제곱) | 역순 입력 |
| 해시 테이블 조회 | O(1) | O(1) | O(n) | 모든 키가 한 버킷에 몰림 |
| BST 탐색 | O(log n) | O(log n) | O(n) | 정렬된 순서로 삽입 |
실무에서 중요한 것은 최악이 나는 조건이 우리 입력에서 흔한지입니다. 정렬된 데이터를 그대로 넣는 일은 아주 흔하므로 퀵 정렬은 피벗을 무작위로 고르거나 중간값을 쓰고, BST는 균형 트리를 씁니다.
흔한 실수: 평균만 보고 안심하는 것. 공격자가 입력을 조작할 수 있는 자리(해시 충돌 공격)에서는 최악이 곧 취약점입니다.
Q.Big-O에서 상수를 무시하는 이유는?
입력이 커질 때 어느 항이 결과를 지배하는지만 보려는 표기이기 때문입니다.
3n의 제곱 + 100n + 5000 에서
n=10 300 + 1,000 + 5,000 상수가 가장 크다
n=1,000 300만 + 10만 + 5,000 제곱 항이 지배한다
n=100,000 3조 + 1,000만 + 5,000 나머지는 오차 수준
규모가 커지면 낮은 차수와 상수의 몫이 사라지므로, 차수만 남겨도 성장 속도를 비교할 수 있습니다. 하드웨어나 언어가 바뀌면 상수는 달라지지만 차수는 그대로라는 점도 이유입니다.
흔한 실수: 그래서 상수는 중요하지 않다고 결론짓는 것. n 이 작은 구간에서는 상수가 전부이고, 실무 데이터는 작을 때가 많습니다. 차수로 후보를 좁히고 실제 측정으로 고르는 것이 맞습니다.
먼저 스스로 답해보고 아래 답변과 견줘보세요. 막히는 부분은 문제로 확인할 수 있어요.
읽었으면 문제로 확인해보세요
자료구조 문제를 풀면 틀린 문제가 자동으로 노트에 쌓입니다. 가입 없이 5문제를 먼저 풀어볼 수도 있어요.