시간복잡도란?
시간복잡도(Time Complexity)는 입력 데이터의 크기(n)에 따라 알고리즘이 수행하는 연산량을 나타낸 것입니다.
간단히 말해 "입력이 많아질수록 이 코드가 얼마나 느려질까?"를 수학적으로 표현하는 방법입니다.
Big O Notation (빅오 표기법)이란?
Big O 표기법은 알고리즘의 최악의 실행 시간을 나타내며, 다음과 같은 종류가 있습니다.
| 표기 | 설명 | 예시 |
| O(1) | 상수 시간 – 입력 크기에 관계 없음 | 배열에서 인덱스로 접근 |
| O(log n) | 로그 시간 – 이진 탐색처럼 반씩 줄이는 구조 | 이진 탐색 |
| O(n) | 선형 시간 – 입력이 커지면 비례해서 늘어남 | 전체 탐색 |
| O(n log n) | 대부분의 정렬 알고리즘 성능 | 병합정렬, 퀵정렬 |
| O(n²) | 이중 반복문 등 | 버블정렬, 삽입정렬 |
| O(2ⁿ), O(n!) | 매우 느림 – 완전탐색 | 순열, 조합 |
시간복잡도의 종류와 예시
O(1) – 상수 시간
var first = list[0]; // 인덱스로 바로 접근아무리 데이터가 많아도 딱 한 번만 동작하니까 시간복잡도는 O(1)가 됩니다.
O(n) – 선형 시간
foreach (var item in list)
Debug.Log(item);리스트가 100개면 100번, 1000개면 1000번 반복하므로 O(n)가 됩니다.
O(n²) – 이중 반복
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
Debug.Log(i + ", " + j);한 번에 n × n번이 되므로 O(n²)가 됩니다.
O(log n) – 로그 시간
int BinarySearch(int[] arr, int target)
{
int left = 0, right = arr.Length - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}반으로 줄여가며 검사 이진 탐색기법입니다.
매 반복마다 절반으로 줄여서 찾는 구조이므로 O(log n)이 됩니다.
O(n log n) – 정렬 알고리즘
Merge Sort, Quick Sort, Unity의 List.Sort()정렬할 때 자주 나오는 알고리즘의 시간복잡도는 O(n log n)이 됩니다.
O(2ⁿ), O(n!)
void Fibonacci(int n)
{
if (n <= 1) return;
Fibonacci(n - 1);
Fibonacci(n - 2);
}완전탐색, 재귀 조합, 순열 계산 등은 n = 50 같은 수치를 넣으면 수천~수만 번 반복하기 때문에 매우 비효율적입니다.
비교 예시 (비슷한 코드, 다른 시간복잡도)
bool HasDuplicate(List<int> list)
{
for (int i = 0; i < list.Count; i++)
for (int j = i + 1; j < list.Count; j++)
if (list[i] == list[j]) return true;
return false;
}bool HasDuplicate(List<int> list)
{
HashSet<int> set = new();
foreach (int num in list)
{
if (set.Contains(num)) return true;
set.Add(num);
}
return false;
}어떤 알고리즘이 더 시간복잡도가 작은지 고민해보시길 바랍니다 ㅎㅎ
정답은 맨 아래 두겠습니다!
위에 알고리즘은 O(n²), 아래 알고리즘은 O(n) 입니다.