시간복잡도와 Big-O Notation

개요 — 왜 복잡도를 알아야 하는가?

게임 개발에서 성능은 기능만큼 중요합니다. Unreal Engine은 기본적으로 초당 60프레임을 목표로 하며, 이는 하나의 프레임에 허용되는 시간이 약 16.67ms에 불과하다는 의미입니다.

이 짧은 시간 안에 물리 시뮬레이션, 렌더링, AI 판단, 애니메이션 업데이트가 모두 처리되어야 합니다. 알고리즘 복잡도를 모르면 “기능은 동작하지만 게임이 느린” 상황이 반복됩니다.

상황	복잡도 무지의 결과
적 100명 탐색	O(n²) 루프로 10,000번 연산 발생
아이템 조회	TArray 선형 탐색 대신 TMap을 썼어야 함
AI 경로탐색	매 Tick 전체 탐색으로 프레임 드롭

---

1. 알고리즘 복잡도의 기본 개념

1.1 시간복잡도 (Time Complexity)

시간복잡도는 입력 크기 n에 따라 연산 횟수가 얼마나 증가하는지를 나타냅니다. 실제 실행 시간(ms)이 아닌, 연산 횟수의 증가 패턴을 추상화한 개념입니다.

1.2 공간복잡도 (Space Complexity)

공간복잡도는 알고리즘 실행에 필요한 메모리 사용량이 입력 크기에 따라 어떻게 증가하는지를 나타냅니다. 추가로 사용하는 보조 메모리(보조 공간복잡도)를 기준으로 분석합니다.

1.3 최선·평균·최악의 경우

표기	의미	대표 예시
Big-O (O)	최악의 경우 상한	가장 자주 사용됨
Big-Omega (Ω)	최선의 경우 하한	알고리즘 이론 분석
Big-Theta (Θ)	평균적 정확한 경계	알고리즘 이론 분석

실무에서는 **Big-O (최악의 경우)**를 기준으로 설계하는 것이 안전합니다. 게임에서 최악의 경우가 항상 발생할 수 있기 때문입니다.

---

2. Big-O Notation 핵심 표기법

2.1 O(1) — 상수 시간

입력 크기에 관계없이 항상 일정한 연산 횟수로 처리됩니다.

// TMap은 키 기반 조회가 평균 O(1)
TMap<FString, int32> ItemDamage;
ItemDamage.Add(TEXT("Sword"), 50);
ItemDamage.Add(TEXT("Bow"), 30);

// 아이템 이름으로 데미지 즉시 조회 — O(1)
int32* FoundDamage = ItemDamage.Find(TEXT("Sword"));
if (FoundDamage != nullptr)
{
    UE_LOG(LogTemp, Log, TEXT("Sword Damage: %d"), *FoundDamage);
}

2.2 O(log n) — 로그 시간

입력 크기가 두 배가 되어도 연산 횟수는 1회만 증가합니다. 이진 탐색(Binary Search)이 대표적입니다.

#include <algorithm>
#include <vector>

// 정렬된 배열에서 이진 탐색 — O(log n)
std::vector<int32> SortedLevels = {1, 5, 10, 20, 50, 100};

auto It = std::lower_bound(SortedLevels.begin(), SortedLevels.end(), 20);
if (It != SortedLevels.end() && *It == 20)
{
    UE_LOG(LogTemp, Log, TEXT("Level 20 found at index: %d"),
        static_cast<int32>(It - SortedLevels.begin()));
}
// n=1,000,000 이어도 최대 20번 비교로 탐색 완료

2.3 O(n) — 선형 시간

입력 크기 n에 비례하여 연산 횟수가 증가합니다. 배열 전체 순회가 대표적입니다.

// 모든 적의 체력을 확인 — O(n)
TArray<AActor*> EnemyActors;

int32 AliveCount = 0;
for (AActor* Enemy : EnemyActors)
{
    if (IsValid(Enemy))
    {
        AliveCount++;
    }
}
UE_LOG(LogTemp, Log, TEXT("Alive Enemies: %d"), AliveCount);

2.4 O(n log n) — 선형 로그 시간

정렬 알고리즘의 표준 복잡도입니다. O(n²)보다 훨씬 효율적이며, std::sort와 Unreal의 TArray::Sort가 이 복잡도를 가집니다.

TArray<int32> Scores = {85, 42, 97, 16, 73, 58};

// Unreal TArray 정렬 — O(n log n)
Scores.Sort([](int32 A, int32 B)
{
    return A > B; // 내림차순
});

// 결과: {97, 85, 73, 58, 42, 16}

2.5 O(n²) — 이차 시간

중첩 루프에서 발생합니다. n이 커질수록 급격히 느려지는 위험한 패턴입니다.

// 버블 정렬 — O(n²): 게임 코드에서 절대 사용 금지
void BubbleSort(TArray<int32>& Arr)
{
    const int32 N = Arr.Num();
    for (int32 I = 0; I < N - 1; ++I)
    {
        for (int32 J = 0; J < N - I - 1; ++J)
        {
            if (Arr[J] > Arr[J + 1])
            {
                Arr.SwapMemory(J, J + 1);
            }
        }
    }
    // n=1,000 → 약 500,000번 연산
    // n=10,000 → 약 50,000,000번 연산 (프레임 드롭 확정)
}

2.6 O(2ⁿ) — 지수 시간

입력이 1 증가할 때마다 연산이 두 배로 폭발합니다. 재귀 피보나치가 대표적 예입니다.

// 순수 재귀 피보나치 — O(2^n): 절대 사용 금지
int32 FibonacciNaive(int32 N)
{
    if (N <= 1) return N;
    return FibonacciNaive(N - 1) + FibonacciNaive(N - 2);
    // Fib(50) → 약 2^50 = 1조 번 이상의 호출
}

// 메모이제이션 적용 — O(n)으로 개선
int32 FibonacciMemo(int32 N, TMap<int32, int32>& Cache)
{
    if (N <= 1) return N;
    if (int32* Cached = Cache.Find(N)) return *Cached;

    int32 Result = FibonacciMemo(N - 1, Cache) + FibonacciMemo(N - 2, Cache);
    Cache.Add(N, Result);
    return Result;
}

2.7 복잡도 비교 (n=1,000 기준)

복잡도	연산 횟수	평가
O(1)	1	이상적
O(log n)	~10	우수
O(n)	1,000	양호
O(n log n)	~10,000	허용
O(n²)	1,000,000	위험
O(2ⁿ)	10^301	사용 불가

---

3. 상각 분석 (Amortized Analysis)

상각 분석은 단일 연산이 가끔 O(n)처럼 비싸더라도 **일련의 연산 전체 평균 비용이 O(1)**임을 보여주는 분석 방법입니다. std::vector와 TArray의 동적 배열 확장이 대표적인 예입니다.

// std::vector의 push_back — 상각 O(1)
// 재할당이 발생하는 순간은 O(n)이지만, 용량을 2배씩 늘리므로
// n번 push_back의 전체 복사 횟수 합계 = 1 + 2 + 4 + ... + n ≈ 2n = O(n)
// → 1회 push_back의 상각 비용 = O(n) / n = O(1)

std::vector<int32> Vec;
Vec.reserve(4); // 재할당을 줄이려면 reserve로 사전 예약

for (int32 i = 0; i < 100; ++i)
{
    Vec.push_back(i); // 평균 O(1) 상각
    // 재할당 발생 시점: 크기가 4→8→16→32→64→128...
    // 각 재할당마다 기존 원소 전체 복사 발생
}

상각 분석 vs 최악 케이스

연산	최악 케이스	상각 케이스	설명
vector::push_back	O(n)	O(1)	재할당이 드물게 발생
TMap::Add	O(n)	O(1)	리해싱이 드물게 발생
stack::push	O(n)	O(1)	내부 deque/vector 확장

게임 실전 팁: 배열 크기를 예측할 수 있는 경우 reserve()를 미리 호출하면 재할당 자체를 제거해 최악 케이스를 없앨 수 있습니다.

// Tick에서 동적으로 채우는 임시 배열 — reserve로 재할당 방지
TArray<AActor*> NearbyActors;
NearbyActors.Reserve(64); // 예상 최대 수 사전 예약

GetWorld()->GetActorListFromCollisionQuery(/* ... */, NearbyActors);

---

3.5 숨겨진 복잡도 — 자주 실수하는 패턴

코드를 보면 O(1)처럼 보이지만 실제로는 훨씬 비싼 연산들이 있습니다.

// ===== 함정 1: 문자열 연결의 O(n) 비용 =====
// std::string + 연산은 새 문자열을 할당·복사하므로 O(n)
// 루프에서 반복 시 전체 O(n²)

// 나쁜 예: 로그 문자열 누적 — O(n²)
std::string log = "";
for (const FString& Msg : Messages) // n번 반복
{
    log += TCHAR_TO_UTF8(*Msg); // 매번 새 문자열 할당 및 복사 O(n) → 전체 O(n²)
}

// 좋은 예: std::ostringstream 또는 FString::Join 사용 — O(n)
std::ostringstream oss;
for (const FString& Msg : Messages)
{
    oss << TCHAR_TO_UTF8(*Msg);
}
std::string result = oss.str();

// ===== 함정 2: TArray::Contains — O(n) =====
TArray<int32> ItemIds = {100, 200, 300};
bool bHas = ItemIds.Contains(200); // O(n) 선형 탐색
// 자주 Contains를 호출한다면 TSet으로 교체 → O(1) 평균

// ===== 함정 3: TArray::Insert / RemoveAt — O(n) =====
TArray<int32> Arr = {1, 2, 3, 4, 5};
Arr.Insert(99, 0);    // 앞에 삽입: 기존 원소 전체 이동 O(n)
Arr.RemoveAt(0);      // 앞에서 삭제: 기존 원소 전체 이동 O(n)
// 순서가 중요하지 않다면 RemoveAtSwap(idx)로 O(1) 대체 가능

// ===== 함정 4: GetComponentByClass — O(n) =====
// 매 Tick마다 호출하면 컴포넌트 수에 비례하는 비용 발생
void AMyActor::Tick(float DeltaTime)
{
    // 나쁜 예: Tick마다 컴포넌트 탐색 O(n)
    UHealthComponent* HP = FindComponentByClass<UHealthComponent>();

    // 좋은 예: BeginPlay에서 캐싱 O(1)
    if (CachedHealthComponent) { /* 사용 */ }
}

---

4. C++ 코드 예시 — 복잡도 분석

3.1 배열 탐색 O(n) vs 해시맵 조회 O(1)

// 나쁜 예: TArray에서 이름으로 아이템 탐색 — O(n)
struct FItemData
{
    FString Name;
    int32   Damage;
};

TArray<FItemData> ItemList;

FString TargetName = TEXT("Excalibur");
FItemData* FoundItem = nullptr;
for (FItemData& Item : ItemList)
{
    if (Item.Name == TargetName)
    {
        FoundItem = &Item;
        break;
    }
}

// -------------------------------------------------------

// 좋은 예: TMap을 사용한 이름 기반 조회 — O(1)
TMap<FString, FItemData> ItemMap;

FItemData* FastFound = ItemMap.Find(TEXT("Excalibur")); // 즉시 조회

아이템이 10,000개라면 TArray는 최대 10,000번, TMap은 평균 1번 비교합니다.

3.2 공간복잡도 — 재귀 vs 반복

// 재귀 팩토리얼 — 공간복잡도 O(n): 스택 프레임 n개 쌓임
int64 FactorialRecursive(int32 N)
{
    if (N <= 1) return 1;
    return N * FactorialRecursive(N - 1);
}

// 반복 팩토리얼 — 공간복잡도 O(1): 추가 메모리 없음
int64 FactorialIterative(int32 N)
{
    int64 Result = 1;
    for (int32 I = 2; I <= N; ++I)
    {
        Result *= I;
    }
    return Result;
}

재귀 깊이가 크면 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다. 게임 로직에서 깊은 재귀는 반드시 반복문으로 전환하거나 꼬리 재귀 최적화를 검토해야 합니다.

---

4. Unreal Engine 실전 사례

4.1 TArray vs TMap vs TSet — 컨테이너 선택 가이드

컨테이너	탐색	삽입	삭제	순회	메모리
TArray	O(n)	O(1) 끝 / O(n) 중간	O(n)	O(n)	연속 (캐시 친화적)
TMap	O(1) 평균	O(1) 평균	O(1) 평균	O(n)	해시 테이블
TSet	O(1) 평균	O(1) 평균	O(1) 평균	O(n)	해시 테이블

// 1. 순서가 중요하고 인덱스 접근이 주인 경우 → TArray
TArray<FVector> PatrolPoints;
PatrolPoints.Add(FVector(0, 0, 0));
PatrolPoints.Add(FVector(100, 0, 0));
FVector NextPoint = PatrolPoints[1]; // O(1) 인덱스 접근

// 2. 키-값 매핑이 필요한 경우 → TMap
TMap<int32, FString> PlayerNames;
PlayerNames.Add(1001, TEXT("Hero"));
FString* Name = PlayerNames.Find(1001); // O(1) 조회

// 3. 중복 없는 집합이 필요한 경우 → TSet
TSet<FGameplayTag> ActiveBuffTags;
ActiveBuffTags.Add(FGameplayTag::RequestGameplayTag(TEXT("Buff.Strength")));
bool bHasBuff = ActiveBuffTags.Contains(
    FGameplayTag::RequestGameplayTag(TEXT("Buff.Strength"))); // O(1)

4.2 Tick()에서의 복잡도 — 프레임 예산 관리

60fps 기준 프레임당 허용 시간은 16.67ms입니다. Tick() 내부에 O(n²) 이상의 코드가 있으면 프레임 드롭이 불가피합니다.

// 나쁜 예: Tick에서 모든 적과 모든 투사체 충돌 체크 — O(n * m)
void AGameManager::Tick(float DeltaTime)
{
    Super::Tick(DeltaTime);

    // 적 100명 × 투사체 200개 = 매 프레임 20,000번 비교 → 프레임 드롭
    for (AEnemy* Enemy : AllEnemies)
    {
        for (AProjectile* Proj : AllProjectiles)
        {
            if (Enemy->GetActorLocation().Equals(Proj->GetActorLocation(), 50.f))
            {
                Enemy->TakeDamage(Proj->GetDamage());
            }
        }
    }
}

// 좋은 예: Unreal 물리 엔진의 공간 분할 활용 — O(log n)
void AGameManager::Tick(float DeltaTime)
{
    Super::Tick(DeltaTime);

    TArray<FOverlapResult> OverlapResults;
    FCollisionShape CollisionShape = FCollisionShape::MakeSphere(50.f);

    GetWorld()->OverlapMultiByChannel(
        OverlapResults,
        GetActorLocation(),
        FQuat::Identity,
        ECollisionChannel::ECC_Pawn,
        CollisionShape
    );
}

4.3 AI PathFinding — A* 알고리즘 복잡도

Unreal Engine의 NavigationMesh 기반 A* 경로탐색의 복잡도는 **O(E log V)**입니다. (E: 간선 수, V: 노드 수)

// 올바른 방법: 목표 위치가 크게 변했을 때만 재탐색
void AMyAIController::OnTargetLocationChanged(FVector NewLocation)
{
    const float RepathThreshold = 200.f;
    if (FVector::Dist(LastKnownTargetLocation, NewLocation) > RepathThreshold)
    {
        MoveToLocation(NewLocation);
        LastKnownTargetLocation = NewLocation;
    }
}

4.4 GAS — GameplayTag 조회 복잡도

GAS의 FGameplayTagContainer는 내부적으로 TArray<FGameplayTag>로 구현되어 있으며, HasTag / HasAll 연산은 **O(n * m)**입니다.

// 최적화: 자주 조회되는 태그는 멤버 변수로 캐싱
UPROPERTY()
FGameplayTag CachedStunnedTag;

void AMyCharacter::BeginPlay()
{
    Super::BeginPlay();
    CachedStunnedTag = FGameplayTag::RequestGameplayTag(TEXT("State.Stunned"));
}

---

5. 복잡도 개선 실전 패턴

5.1 캐싱 전략 (Memoization)

UCLASS()
class AMyCharacter : public ACharacter
{
    GENERATED_BODY()

private:
    UPROPERTY()
    TObjectPtr<UStatComponent> CachedStatComponent;

    bool bIsNearEnemyCached = false;
    float NearEnemyCacheTimer = 0.f;
    static constexpr float NearEnemyCacheInterval = 0.2f;

public:
    virtual void BeginPlay() override
    {
        Super::BeginPlay();
        CachedStatComponent = FindComponentByClass<UStatComponent>();
    }

    virtual void Tick(float DeltaTime) override
    {
        Super::Tick(DeltaTime);

        NearEnemyCacheTimer += DeltaTime;
        if (NearEnemyCacheTimer >= NearEnemyCacheInterval)
        {
            NearEnemyCacheTimer = 0.f;
            bIsNearEnemyCached = CheckNearEnemies();
        }

        if (bIsNearEnemyCached)
        {
            // 전투 로직
        }
    }
};

5.2 공간복잡도 vs 시간복잡도 트레이드오프

전략	시간복잡도	공간복잡도	사용 시점
순수 재계산	O(n)	O(1)	메모리 제약이 심한 경우
결과 캐싱	O(1)	O(n)	동일 입력이 자주 반복되는 경우
공간 분할 자료구조	O(log n)	O(n)	대규모 씬 공간 탐색
사전 정렬 + 이진 탐색	O(log n)	O(n)	정적 데이터 반복 탐색

---

6. 정리 및 체크리스트

복잡도 빠른 참조표

코드 패턴	복잡도
배열 인덱스 접근 Arr[i]	O(1)
TMap/TSet 조회	O(1) 평균
TArray 선형 탐색	O(n)
정렬된 배열 이진 탐색	O(log n)
TArray::Sort	O(n log n)
중첩 for 루프	O(n²)
순수 재귀 피보나치	O(2ⁿ)

게임 개발 복잡도 체크리스트

• Tick() 내부에 O(n²) 이상의 중첩 루프가 없는가?
• 이름/ID 기반 탐색이 필요하면 TMap을 사용하고 있는가?
• GetComponentByClass, FindActor 등 비용 큰 탐색은 BeginPlay에서 캐싱했는가?
• 물리 충돌 탐색은 직접 구현 대신 OverlapMultiByChannel을 사용하는가?
• AI 경로 재탐색은 위치 변화가 충분할 때만 호출하는가?
• GameplayTag는 BeginPlay에서 캐싱하여 반복 RequestGameplayTag 호출을 최소화했는가?
• 깊은 재귀는 반복문으로 전환하거나 공간복잡도를 확인했는가?