시간복잡도 (time complexity)

프로그램이 얼마나 빠르게 실행되는지를 판단할 때 가장 많이 사용하는 개념이 시간복잡도다. 코드 실행 시간을 직접 재는 대신, 입력 크기(N) 가 커질수록 걸리는 시간이 어떻게 증가하는지를 수학적으로 표현한 것이 시간복잡도다.

---

1. 시간복잡도가 필요한 이유

• 실제 실행 시간은 컴퓨터 성능, CPU 상태, 운영체제 등 환경에 따라 달라진다.
• 하지만 알고리즘의 ‘성능’을 비교하려면 환경에 영향을 받지 않는 공통 기준이 필요하다.
• 그래서 입력 크기가 커질 때 시간이 증가하는 패턴을 기준으로 알고리즘을 비교한다.

---

2. Big-O 표기법(O 표기법)

가장 많이 쓰는 시간복잡도 표기법이며, 가장 빠르게 증가하는 항만 남기고 나머지는 버린 형태로 표현한다.

표기	의미	예시
O(1)	상수 시간	배열에서 인덱스로 값 꺼내기
O(log N)	로그 시간	이진 탐색
O(N)	선형 시간	for문 한 번
O(N log N)	로그 곱	정렬 알고리즘(퀵/합병/힙)
O(N²)	제곱	이중 for문
O(2ⁿ)	지수	부분집합, 백트래킹
O(N!)	팩토리얼	순열 생성

---

3. 시간복잡도 직관적으로 이해하기

O(1)

입력 크기와 상관없이 항상 일정한 시간.

int x = arr[5];   // 배열 인덱싱

O(N)

입력 크기만큼 작업 반복.

for (int i = 0; i < N; i++) { ... }

O(N²)

N이 커질수록 작업량이 기하급수적으로 증가.
이중 반복문이 대표적.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) { ... }
}

O(log N)

전체 범위를 절반씩 줄여가며 탐색.
이진 탐색(Binary Search) 등이 여기에 해당.

O(N log N)

정렬 알고리즘에서 자주 등장하며, 효율적인 알고리즘의 기준값으로 여겨진다.

---

4. 시간복잡도 계산 기본 공식

1) 가장 많이 반복되는 부분에 집중

전체 시간에서 가장 큰 영향을 미치는 부분만 고려한다.

2) 상수는 버린다

예: O(2N) → O(N)

3) 가장 큰 차수만 남긴다

예: O(N² + N) → O(N²)

---

5. 실전 예제

예제 1. 이중 반복문

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        cout << i << j << endl;
    }
}

반복 횟수: N × N = N²
시간복잡도: O(N²)

예제 2. 절반씩 줄이는 반복

int x = N;
while (x > 1) {
    x /= 2;
}

반복 횟수: log₂(N)
시간복잡도: O(log N)

---

6. 왜 시간복잡도를 알아야 할까?

• 코드가 입력 크기 증가에 버틸 수 있는지 판단할 수 있다.
• 최적화된 게임 엔진, 서버, 데이터 처리 시스템 개발에서 필수.
• C++, Unreal Engine처럼 성능이 중요한 분야에서는 더욱 중요.

---

정리

• 시간복잡도 = 입력 크기(N)에 따라 증가하는 연산량을 수학적으로 표현한 것
• 가장 중요한 개념은 Big-O 표기법
• 목표는 빠른 알고리즘, 즉 성능 좋은 코드 구조를 만드는 것

---