12. 시간복잡도란?

 

 

"시간복잡도"

 

개발을 하다보면 같은 기능인데도 어떤 구현은 가볍게 돌아가고,

어떤 구현은 데이터가 조금만 늘어도 갑자기 버벅이는 경우가 있다.

이 차이를 설명해주는 것이 시간복잡도(Time Complexity)이고, 우리는 보통 Big-O 표기법으로 표현한다.

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

1) 시간복잡도란?

 

시간복잡도는 실행 시간(ms) 자체가 아니라, 

입력 크기 n이 커질 때 필요한 연산 수가 어떻게 증가하는지를 말한다.

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

2) 왜 중요한가?

 

Unity 관점에서 본다면,
Unity는 프레임 단위로 돌아가고, 60fps 기준 1프레임 예산은 약 16.67ms.
Update에서 O(n²) 같은 패턴이 숨어 있으면, 오브젝트 수가 늘어나는 순간 프레임이 깨진다.

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

 

3) Big-O 표기법이란?

 

입력 크기 n이 커질 때 

알고리즘의 실행 시간(또는 메모리 사용량)이 

얼마나 빠르게 증가하는지(성장률)를 나타내는 표기법

 

O(1): 입력 크기와 무관 (상수 시간)

O(log n): 절반씩 줄어듦 (이진 탐색)

O(n): 한 번 순회 (단일 루프)

O(n log n): 정렬/분할정복 계열

O(n²): 이중 루프(모든 쌍 비교)

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

4) 최악 시간복잡도 vs 평균 시간복잡도

 

 

최악 시간복잡도 (Worst Case)

가장 불리한 입력/상황에서 걸리는 시간

상한(upper bound) 개념이라,

'이 정도는 절대 넘지 않는다'를 보장한다.

게임/실시간(프레임 예산)에서는 스파이크 방지 때문에 중요하다.

 

예시)
선형 탐색: 못 찾는 경우가 최악 → O(n)
퀵정렬: 피벗이 계속 나쁘면 최악 → O(n²)

 

 

 

평균 시간복잡도 (Average Case)

일반적인 입력이 들어온다고 가정했을 때의 기대 성능(기댓값)
(단, 평균은 입력 분포 가정이 들어가므로, 실제 데이터가 편향되어 있으면 평균과 다르게 나올 수 있다.)

 

예시)
해시 기반(Dictionary/HashSet): 보통(평균) 조회가 빠름 → 평균 O(1)
(구현/상황에 따라 충돌이 심해지면 최악은 더 나빠질 수 있음)

 

 

 

+++

 

간단 한줄 정리

 

평균:

대부분의 경우 얼마나 빠른가

(기대 성능)

최악:

운이 나빠도 어디까지 느려질 수 있나

(상한/안전선)

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

5) C# 컬렉션과 시간복잡도(선택 기준)

 

자료구조 선택은 곧 시간복잡도 선택이다.

특히 Unity에서는 매 프레임 호출되는지 여부가 매우 중요하다.

 

키로 빠르게 찾기 → Dictionary, HashSet (평균 O(1))

순회/인덱싱 중심 → List (인덱스 O(1), Contains는 O(n))

정렬된 순회가 필요 → SortedDictionary/SortedSet (O(log n))

 

 

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

 

6) 오늘의 한 줄 요약

 

『  시간복잡도는 입력 크기 n이 커질 때 연산량이 얼마나 빨리 증가하는지(성장률)를 나타내는 지표다. 』