# 시간복잡도

분야: CS·데이터사이언스
학교급: 고등
정식 URL: https://pi.devxdev.xyz/wiki/math/%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84

---

<!-- prereq: 함수, 로그, 지수함수 -->

## 정의

**시간복잡도**(time complexity)는 어떤 알고리즘이 입력의 크기 $n$에 대해 수행하는 연산의 횟수를 $n$에 대한 함수로 나타낸 것이다. 실제 실행 시간(초 단위)은 컴퓨터 성능에 따라 달라지므로, 대신 입력 크기가 커질 때 연산 횟수가 얼마나 빠르게 늘어나는지를 함수의 **증가 속도**로 표현한다.

이때 정확한 계수나 낮은 차수의 항은 무시하고 가장 빠르게 증가하는 항만 남겨서 상한을 나타내는데, 이를 **빅오 표기법**(Big-O notation)이라 한다. 함수 $f(n)$과 $g(n)$에 대해

$$f(n) = O(g(n))$$

($f(n)$은 $g(n)$의 빅오라 읽는다)라는 것은, 어떤 양의 상수 $c$와 $n_0$가 존재하여 $n \ge n_0$인 모든 $n$에 대해 $f(n) \le c \cdot g(n)$이 성립함을 뜻한다. 즉 $g(n)$은 $f(n)$이 커지는 속도의 상한을 나타낸다.

## 직관

친구 이름이 적힌 명부에서 특정 이름을 찾는 상황을 생각해 보자. 앞에서부터 한 명씩 확인하면 명부가 두 배로 길어질 때 확인 횟수도 두 배로 늘어난다 — 이것이 $O(n)$이다. 반면 명부가 이름 순으로 정렬되어 있어서 이진 탐색처럼 절반씩 줄여가며 찾으면, 명부가 두 배로 길어져도 확인 횟수는 겨우 1번 더 늘어난다 — 이것이 $O(\log n)$이다.

시간복잡도는 "$n$이 작을 때 몇 초 걸리는가"가 아니라 "$n$이 아주 커질 때 걸리는 시간이 얼마나 폭발적으로 늘어나는가"를 비교하는 도구다. 마치 함수의 극한처럼, $n \to \infty$일 때의 경향성을 본다.

## 자주 쓰이는 시간복잡도

| 표기 | 읽는 법 | 예 |
|---|---|---|
| $O(1)$ | 오 원 | 배열의 특정 위치 값 읽기 |
| $O(\log n)$ | 오 로그 엔 | 이진 탐색 |
| $O(n)$ | 오 엔 | 선형 탐색(처음부터 끝까지 한 번씩 확인) |
| $O(n \log n)$ | 오 엔 로그 엔 | 병합 정렬 등 |
| $O(n^2)$ | 오 엔의 제곱 | 이중 반복문(모든 쌍 비교) |
| $O(2^n)$ | 오 이의 엔 제곱 | 모든 부분집합을 나열하는 경우 |

## 예시

배열의 크기가 $n=1{,}000{,}000$일 때 원하는 값을 찾는 두 방법을 비교하자.

- 선형 탐색: 최악의 경우 $n = 1{,}000{,}000$번 비교해야 한다. 시간복잡도는 $O(n)$이다.
- 이진 탐색: 한 번 비교할 때마다 탐색 범위가 절반으로 줄어드므로, 필요한 비교 횟수는 $\log_2 n$에 가깝다. $\log_2 1{,}000{,}000 \approx 19.9$이므로 최대 약 20번이면 충분하다.

같은 문제를 $O(n)$과 $O(\log n)$으로 풀 때 걸리는 횟수의 차이가 $n$이 커질수록 얼마나 벌어지는지, 아래 그래프로 $n$, $n\log n$, $n^2$의 증가 속도를 비교해 보자.


그래프: y=x, y=x*log(x), y=x^2 (정의역 1~20)


## 🌍 실생활 예시

온라인 쇼핑몰에서 상품 수백만 개 중 특정 상품을 검색할 때, 상품이 이름이나 가격 순으로 미리 정렬되어 있으면 이진 탐색과 같은 $O(\log n)$ 방식으로 순식간에 찾을 수 있다. 만약 정렬 없이 하나씩 확인하는 $O(n)$ 방식을 쓴다면, 상품 수가 늘어날수록 검색창의 응답 속도가 눈에 띄게 느려진다. 실제 검색 엔진과 데이터베이스 색인(index)이 정렬·트리 구조를 유지하는 이유가 바로 이 시간복잡도 차이 때문이다.

## ⚠️ 흔한 실수

- **잘못된 생각**: "반복문(for문)이 없으면 시간복잡도는 항상 $O(1)$이다." → 재귀 알고리즘처럼 반복문 없이 함수가 자기 자신을 여러 번 호출하는 경우도 호출 횟수를 세어야 한다. 예를 들어 재귀로 구현한 피보나치수열 계산은 반복문이 없어도 $O(2^n)$에 가까운 시간이 걸릴 수 있다.
- **잘못된 생각**: "$O(2n)$과 $O(n)$은 계수가 다르니 서로 다른 시간복잡도다." → 빅오 표기에서는 상수배를 무시하므로 $O(2n) = O(n)$이다. $n$이 충분히 커지면 $2n$과 $n$은 같은 속도로 증가한다고 보기 때문이다.
- **잘못된 생각**: "$O(n^2)$인 알고리즘은 $O(n\log n)$인 알고리즘보다 항상 느리다." → 빅오는 $n$이 아주 커질 때($n \to \infty$)의 경향만 보장한다. $n$이 작으면 상수항이나 낮은 차수 항의 영향으로 $O(n^2)$ 알고리즘이 특정 구간에서 더 빠를 수도 있다.

## 확인 문제

1. 크기 $n=1{,}024$인 정렬된 배열에서 이진 탐색으로 원하는 값을 찾으려 한다. 최대 몇 번 비교해야 하는지 구하고, 배열 크기가 $n=2{,}048$로 두 배가 되면 비교 횟수가 어떻게 변하는지 설명하시오. (이 문제를 풀면서 왜 $O(\log n)$이 $O(n)$보다 훨씬 빠른지 직접 느껴 보자.)
2. 다음 코드의 시간복잡도를 빅오 표기로 나타내시오.
   ```
   for i in 1..n:
       for j in 1..n:
           출력(i, j)
   ```
3. $f(n) = 3n^2 + 5n + 2$일 때 $f(n) = O(n^2)$임을 정의를 이용해 설명하시오. (즉, 어떤 상수 $c$와 $n_0$를 잡으면 $f(n) \le c \cdot n^2$이 항상 성립하는지 확인하시오.)

정답 보기:

1. $\log_2 1{,}024 = 10$이므로 최대 10번 비교하면 된다. 배열 크기가 두 배인 $2{,}048$이 되어도 $\log_2 2{,}048 = 11$이므로 비교 횟수는 1번만 늘어난다. 크기가 두 배가 될 때 비교 횟수는 겨우 1씩 늘어나는 것이 로그의 특징이다.
2. 바깥 반복문이 $n$번, 안쪽 반복문도 각각 $n$번 실행되므로 총 실행 횟수는 $n \times n = n^2$번이다. 시간복잡도는 $O(n^2)$이다.
3. $n \ge 1$일 때 $3n^2 + 5n + 2 \le 3n^2 + 5n^2 + 2n^2 = 10n^2$이 성립한다. 따라서 $c=10$, $n_0=1$로 잡으면 모든 $n \ge n_0$에서 $f(n) \le c \cdot n^2$이 성립하므로 $f(n) = O(n^2)$이다.



## 관련 개념

- 함수 — 시간복잡도는 입력 크기 $n$에 대한 함수로 표현된다.
- 로그 — $O(\log n)$ 복잡도의 증가 속도를 이해하려면 로그의 성질이 필요하다.
- 지수함수 — $O(2^n)$처럼 지수적으로 증가하는 경우와 비교하는 데 쓰인다.
- 이진 탐색 — $O(\log n)$ 시간복잡도를 갖는 대표적인 알고리즘이다.
- 재귀 알고리즘 — 재귀로 구현된 알고리즘의 시간복잡도를 분석할 때 함께 다룬다.

---

관련 개념:
- 이진 탐색 (/wiki/math/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89)
- 재귀 알고리즘 (/wiki/math/%EC%9E%AC%EA%B7%80_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)
- 함수 (/wiki/math/%ED%95%A8%EC%88%98)
- 로그 (/wiki/math/%EB%A1%9C%EA%B7%B8)
- 지수함수 (/wiki/math/%EC%A7%80%EC%88%98%ED%95%A8%EC%88%98)