시간복잡도

CS·데이터사이언스 고등 · v1 · 🤖 LLM 버전

정의

시간복잡도(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$일 때의 경향성을 본다.

자주 쓰이는 시간복잡도

예시

배열의 크기가 $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$의 증가 속도를 비교해 보자.

🌍 실생활 예시

온라인 쇼핑몰에서 상품 수백만 개 중 특정 상품을 검색할 때, 상품이 이름이나 가격 순으로 미리 정렬되어 있으면 이진 탐색과 같은 $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$이 항상 성립하는지 확인하시오.)

관련 개념

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