이 글에서 얻는 것
- 시간복잡도(Big-O)를 “암기”가 아니라 선택 기준으로 쓸 수 있습니다.
- 평균/최악/상환(amortized) 복잡도의 차이를 알고, 실무에서 흔히 놓치는 함정을 피합니다.
- HashMap/TreeMap/Heap 같은 자료구조를 백엔드 사용 사례(캐시, 집계, Top-K, 정렬 필요 여부) 로 연결합니다.
- 성능 이슈가 났을 때 “복잡도 문제인지 / 상수항·메모리·GC 문제인지”를 구분할 힌트를 얻습니다.
0) Big-O를 제대로 쓰는 법 (짧게)
Big-O는 “절대 시간”이 아니라 입력 크기(n)가 커질 때 증가율을 말합니다.
O(n)이 항상 느린 건 아닙니다. n이 작으면O(n)이O(log n)보다 빠를 수도 있습니다(상수항/캐시 적중).- 평균이
O(1)인 구조도 최악은 O(n) 이 될 수 있습니다(HashMap 충돌, 리사이즈, 편향된 입력). - 컬렉션의
add가O(1)이라도 종종 상환(amortized) O(1) 인 경우가 있습니다(배열 확장 비용을 나눠 가짐).
1) 복잡도 표(기본)
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 | 비고 |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | 랜덤 접근 빠름 |
| ArrayList | O(1) | O(n) | O(n) | O(n) | 끝 삽입 amortized O(1) |
| LinkedList | O(n) | O(n) | O(1) | O(1) | 양 끝/노드 기준 삽입·삭제 |
| Stack/Queue | O(1) | O(n) | O(1) | O(1) | |
| HashMap | O(1) | O(1) | O(1) | O(1) | 해시 충돌 시 최악 O(n) |
| TreeMap | O(log n) | O(log n) | O(log n) | O(log n) | 정렬 유지 |
| Heap | O(1) | O(n) | O(log n) | O(log n) | 우선순위 큐 |
| Union-Find | - | α(n) | α(n) | α(n) | 거의 O(1), path compression |
| Graph (Adj List) | - | O(V+E) | O(1) | O(1) | BFS/DFS: O(V+E) |
표는 출발점일 뿐이고, 실제 선택은 “내가 자주 하는 연산이 뭔지”로 결정합니다.
2) 실무 선택 가이드(자주 쓰는 기준)
Map/Set: 정렬이 필요하냐?
- 정렬/범위 조회가 필요 없다 → 기본은
HashMap/HashSet - “키 순서 유지/범위 조회/근접값”이 필요하다 →
TreeMap/TreeSet - “삽입 순서 유지”가 필요하다 →
LinkedHashMap(LRU 캐시의 기반)
Top-K / 우선순위
- “가장 큰/작은 값 K개” 같은 문제 →
Heap(PriorityQueue) - 스트리밍 집계에서 Top-K를 유지할 때는 “전체 정렬”보다 힙이 훨씬 효율적입니다.
큐/버퍼
- 단순 FIFO 큐는
ArrayDeque가 대부분의 경우LinkedList보다 낫습니다(메모리/캐시 친화).
3) 흔한 함정(복잡도만 보고 결정하면 생기는 문제)
LinkedList가 O(1) 삽입이라서 빠르다?
노드를 “이미 알고 있을 때” 삽입/삭제가 O(1)인 것이지, 대부분의 실무 코드는 먼저 위치를 찾기 위해 O(n) 탐색을 합니다. 그리고 노드 객체가 많아지면 포인터 추적 비용/GC 부담이 커져 오히려 느려질 때가 많습니다.
HashMap은 무조건 O(1)이다?
평균은 O(1)이지만 다음 상황에서 비용이 튀기 쉽습니다.
- 리사이즈(버킷 재배치)로 인한 순간적인 스파이크
- 해시 품질/입력 편향으로 충돌이 늘어나는 경우
- 많은 객체 키/값으로 인한 힙 사용량 증가 → GC 압박
4) 백엔드에서 ‘복잡도 문제’가 실제로 나타나는 형태
- 목록 API가 “n이 커질수록” 선형으로 느려진다 → 보통 O(n²) 루프/중첩 조회(N+1) 가능성
- 캐시/집계 테이블이 커질수록 지연이 증가한다 → 자료구조 선택 + 동시성(락/경합) 문제 가능성
- 특정 시점에만 갑자기 느려진다 → HashMap 리사이즈/GC/락 경합 같은 “스파이크” 가능성
5) 성능 비교를 해보고 싶다면(짧게)
마이크로 벤치마크는 쉽게 오해합니다. 가능하면 JMH를 쓰고, 최소한 아래를 지키세요.
- 워밍업 없이 “한 번 재고 결론” 내리지 않기(JIT/캐시 영향)
System.nanoTime()로 단일 측정하지 않기(잡음이 큼)- “시간”만 보지 말고 메모리/GC/할당량도 같이 보기
연습(추천)
- HashMap vs TreeMap을 “정렬 필요/범위 조회” 관점에서 비교하고, 어떤 상황에서 TreeMap이 더 나은지 사례를 적어보기
- PriorityQueue로 Top-K를 구현하고, 전체 정렬과 비교해서 연산 횟수가 어떻게 달라지는지 적어보기
- Union-Find로 “연결 요소” 문제를 풀고, path compression이 왜 효과적인지 설명해보기
💬 댓글