자료구조나 알고리즘을 설명할 때 빠지지 않고 등장하는 표현이 바로 O(1), O(n), O(log n) 과 같은 시간 복잡도(Time Complexity)입니다.
이 글은 모든 자료구조 문서에서 반복적으로 등장하는 Big O 표기법의 기준을 설명하기 위한 개념 정리 문서입니다. Unity 개발자가 자료구조를 이해하는 데 필요한 관점만을 중심으로 정리합니다.
1. 시간 복잡도(Big O)란?
시간 복잡도(Big O 표기법)는 입력 데이터의 크기(n)가 증가할 때, 연산 횟수가 어떤 방식(선형, 로그, 제곱 등)으로 증가하는지를 나타내는 표기법입니다.
중요한 점은 Big O가 실제 실행 시간(ms)을 의미하지 않는다는 것입니다.
- [X] 몇 ms가 걸리는지
- [X] 어떤 CPU가 더 빠른지
2. 왜 Big O를 사용하는가?
같은 기능을 하는 코드라도 구현 방식에 따라 성능 차이가 크게 발생할 수 있습니다.
Big O는 다음과 같은 이유로 사용됩니다.
- 하드웨어 성능 차이를 배제하기 위해
- 언어(C#, C++, Java)의 차이를 배제하기 위해
- 구조적으로 어떤 방식이 더 효율적인지 비교하기 위해
즉, Big O는 특정 시점에서 코드가 빠른지 느린지를 판단하기 위한 기준이 아니라, 데이터의 양이 증가하더라도 성능이 예측 가능하게 유지되는지를 판단하기 위한 기준입니다.
3. n은 무엇을 의미하는가?
Big O에서 등장하는 n은 보통 다음을 의미합니다.
- 배열이나 리스트의 요소 개수
- 트리의 노드 수
- 큐나 힙에 들어 있는 데이터 개수
즉, 현재 처리해야 할 데이터의 크기라고 생각하시면 됩니다.
4. 자주 등장하는 Big O 표기
실무와 자료구조 설명에서 자주 사용하는 Big O는 다음 정도면 충분합니다.
| 표기 | 의미 | 예시 |
|---|---|---|
| O(1) | 상수 시간 | 배열 인덱스 접근 |
| O(n) | 선형 시간 | 리스트 전체 순회 |
| O(log n) | 로그 시간 | 이진 탐색, 균형 트리 |
| O(n log n) | 준선형 | 정렬 알고리즘 |
| O(n²) | 제곱 시간 | 이중 반복문 |
이 시리즈에서는 O(2ⁿ), O(n!) 같은 고급 알고리즘 복잡도는 다루지 않습니다.
- 가로축(Input Size) : 입력 데이터 크기 (개수)
- 세로축(Computations) : 연산 횟수
5. O(log n) 구조의 특징
O(log n)은 데이터가 늘어날수록 탐색 범위를 절반씩 줄이는 구조에서 등장합니다.
대표적인 예시는 다음과 같습니다.
데이터가 1,000개 → 10,000개 → 1,000,000개로 늘어나도 연산 횟수는 아주 완만하게 증가합니다.
이 때문에 대규모 데이터 처리에서는 O(log n) 구조가 매우 중요합니다.
6. 평균 시간과 최악 시간
자료구조를 설명할 때는 보통 두 가지 관점이 등장합니다.
- Average Case : 평균적인 상황
- Worst Case : 최악의 상황
예를 들어 Binary Search Tree(BST)는:
- 평균적으로는 O(log n)
- 트리가 한쪽으로 치우치면 O(n)
이 문제를 해결하기 위해 등장한 것이 AVL Tree, Red-Black Tree 같은 균형 트리입니다.
7. Unity 개발에서 시간 복잡도를 고려해야 하는 이유
Unity 프로젝트에서는 작은 테스트 환경에서는 문제가 없던 코드가, 실제 서비스 단계에서 갑자기 성능 문제를 일으키는 경우가 많습니다. 예를 들어 Update()에서 매 프레임마다 List 전체를 순회하거나, Find 계열 API를 반복 호출하는 코드는 데이터 수가 늘어날수록 프레임 드랍의 원인이 됩니다.
이런 문제를 사전에 방지하려면, 단순히 코드가 동작하는지 여부뿐 아니라 자료구조 선택 단계에서 시간 복잡도를 함께 고려해야 합니다.
8. 시간 복잡도에 대해 자주 하는 오해
- O(1)은 항상 빠르다
O(1)은 입력 크기에 따라 연산 횟수가 증가하지 않는다는 의미이지, 실제 실행 시간이 항상 빠르다는 뜻은 아닙니다. 연산 자체의 비용(상수 비용)과 호출 빈도에 따라 체감 성능은 달라질 수 있습니다. - O(n)은 무조건 느리다
데이터의 크기가 작거나, 호출 빈도가 낮은 경우에는 O(n) 구조도 충분히 빠르게 동작할 수 있습니다. - Big O는 실제 실행 시간을 보장한다
Big O는 실제 실행 시간을 예측하는 지표가 아니라, 입력 데이터가 증가할 때 성능이 어떻게 변하는지를 설명하는 표기법입니다.
따라서 Big O는 절대적인 성능 지표가 아니라, 자료구조와 알고리즘을 선택하기 위한 판단 기준으로 사용하는 것이 중요합니다.
8.1 Unity 개발 관점 예시: O(1)인데도 느릴 수 있는 경우
시간 복잡도를 처음 접하면 이런 오해를 하기 쉽습니다.
“Dictionary는 O(1)이니까 Update()에서 막 써도 되겠지?”
하지만 Unity에서는 다음 조건이 겹치면 O(1) 연산도 충분히 병목이 될 수 있습니다.
- Update()에서 매 프레임 실행된다
- Dictionary 접근이 수천 번 반복된다
- 모바일처럼 성능 여유가 적은 환경이다
Big O에서 O(1)은 데이터 크기와 무관하다는 의미이지, 연산이 가볍다는 것을 보장하지는 않습니다. 즉, Big O는 늘어나는 양(증가 추세)만 설명하고, 한 번의 연산이 얼마나 무거운지(상수 비용)까지는 설명하지 않습니다.
Unity 개발에서는 시간 복잡도와 함께 호출 빈도와 실행 환경을 반드시 함께 고려해야 합니다.
9. 자료구조별 시간 복잡도 요약
| 자료구조 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|
| Array / List | O(n) | O(n) | O(n) |
| LinkedList | O(n) | O(1) | O(1) |
| HashSet / Dictionary | O(1) | O(1) | O(1) |
| BST | O(n) | O(n) | O(n) |
| AVL / Red-Black Tree | O(log n) | O(log n) | O(log n) |
| Heap | O(n) | O(log n) | O(log n) |
※ Hash 기반 자료구조의 O(1)은 평균 시간 복잡도를 의미하며, 충돌이 극단적으로 발생하는 경우 최악의 경우 O(n)이 될 수 있습니다.
※ Heap에서의 탐색은 임의 값 검색을 의미하며, 최대/최소 값을 꺼내는 연산은 O(1)입니다.
마무리
Big O는 암기해야 할 공식이 아니라, 자료구조의 성능 특성을 이해하고 비교하기 위한 사고 기준입니다. 시간 복잡도를 통해, 어떤 구조가 데이터의 증가에 강한지, 어떤 상황에서 성능 문제가 발생할 수 있는지를 보다 명확하게 판단할 수 있습니다.
이 글에서 정리한 Big O 개념이, 자료구조를 선택하거나 설계할 때 성능 관점에서 한 번 더 생각해 보는 기준점이 되기를 바랍니다.
※ 다음 글에서는 정렬(Sorting) 개념을 살펴보며, 다양한 정렬 알고리즘을 이해하기 전에 알아야 할 정렬의 목적과 기준, 그리고 시간 복잡도가 정렬 성능에 어떤 의미를 가지는지를 정리합니다.
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 C# Bubble Sort(버블 정렬) 구현 (0) | 2026.01.14 |
|---|---|
| Unity 개발자를 위한 정렬(Sort) 개념과 시간 복잡도 이해 (0) | 2026.01.13 |
| Unity 개발자를 위한 C# Red-Black Tree(레드 블랙 트리) 구현 (0) | 2025.12.27 |
| Unity 개발자를 위한 C# AVL(자기 균형 이진 탐색 트리) 구현 (0) | 2025.12.24 |
| Unity 개발자를 위한 C# BST(Binary Search Tree, 이진 탐색 트리) 구현 (0) | 2025.12.11 |
