시간 복잡도 (Time Complexity)

정의

시간 복잡도 (Time Complexity) 는 입력 크기 N 이 증가할 때 알고리즘의 연산 횟수 증가율 을 나타낸다. PS 에서는 주로 최악 케이스 Big-O 표기법 을 사용.

한 줄 요약: “N 이 충분히 클 때 실행 시간이 얼마나 빠르게 늘어나는가”.

점근적 표기법

세 가지 표기법이 있으며, 각각 상한, 양면 한계, 하한 을 나타낸다.

Big-O (상한, Upper Bound)

$f(n)=O(g(n))⟺\exists c>0,n_0\text{{}s.t.\}f(n)\le c\cdot g(n)\text{{}forall\}n>n_0$

“충분히 큰 n 에서 f(n) 이 c·g(n) 보다 크지 않다”. PS 에서 가장 많이 쓰는 표기법.

Big-Omega (하한, Lower Bound)

$f(n)=\Omega (g(n))⟺\exists c>0,n_0\text{{}s.t.\}f(n)\ge c\cdot g(n)\text{{}forall\}n>n_0$

“f(n) 이 c·g(n) 보다 항상 크다”. 알고리즘의 최선 케이스 또는 문제의 최적 하한 표현.

Big-Theta (양면 한계, Tight Bound)

$f(n)=\Theta (g(n))⟺f(n)=O(g(n))\text{{}and\}f(n)=\Omega (g(n))$

“f(n) 이 g(n) 과 동일한 성장률”. 마스터 정리 에서 Θ 를 사용.

시각화

복잡도 성장 비교

flowchart LR
    A["O(1)<br/>해시 조회, 배열 접근"]
    B["O(log N)<br/>이분 탐색, 균형 트리"]
    C["O(N)<br/>선형 탐색, 누적 합"]
    D["O(N log N)<br/>병합 정렬, 힙 정렬"]
    E["O(N^2)<br/>버블 정렬, 나이브 DP"]
    F["O(2^N)<br/>부분집합, 백트래킹"]
    G["O(N!)<br/>순열 완전 탐색"]
    A --> B --> C --> D --> E --> F --> G

오른쪽으로 갈수록 빠르게 증가. N=20 기준으로 O(2^20) = 1,048,576, O(20!) = 2.4×10^18.

대회 제한별 허용 복잡도

flowchart LR
    N["입력 N"]
    N --> L1["N 12이하: O(N!) 허용"]
    N --> L2["N 25이하: O(2^N) 허용"]
    N --> L3["N 500이하: O(N^3) 허용"]
    N --> L4["N 5000이하: O(N^2) 허용"]
    N --> L5["N 30만이하: O(N log N) 허용"]
    N --> L6["N 10^8이하: O(N) 허용"]

대표 복잡도별 예시

PS 에서는 “1초 = 약 10^8 ~ 10^9 연산” 을 기준으로 사용.

대회 제한과 실처리량

10^8 연산/초 를 기준으로 한 허용 N 크기:

C++ 에서 단순 덧셈 루프는 10^9 연산/초도 가능하지만, 해시 테이블 조회나 포인터 추적은 10^7 ~ 10^8 수준. 메모리 접근 패턴이 성능에 큰 영향.

Amortized 복잡도

분할 상환 분석 (Amortized Analysis) 은 개별 연산이 아닌 N번 연산의 총 비용 / N 으로 평균 복잡도를 구한다.

대표 예: 동적 배열 push_back

• capacity 1에서 시작, push_back N번:

  • 재할당 시점: 1, 2, 4, 8, …, N
  • 복사 비용 합계: 1 + 2 + 4 + … + N = 2N - 1 = O(N)
  • 일반 삽입 비용: N번 × O(1) = O(N)
  • 총합: O(N) → 1회 평균 O(1)

• 개별 push_back 은 재할당 시 O(N) 일 수 있지만, N번 실행 시 평균 O(1).

다른 예: 병합 정렬 은 모든 단계에서 O(N) 비용이 log N 번 → O(N log N).

복잡도 분석 절차

실전에서 알고리즘 복잡도를 빠르게 분석하는 절차:

1. 루프 구조 파악
   - 단일 루프 O(1~N): 대부분 O(N)
   - 이중 루프: O(N^2) (단, 내부가 분기로 O(1) 이면 O(N))
   - log 분할 (이분 탐색 패턴): O(log N)

2. 재귀 점화식 파악
   - T(n) = 2T(n/2) + O(n): 마스터 정리 -> O(N log N)
   - T(n) = T(n-1) + O(1): O(N)
   - T(n) = 2T(n-1) + O(1): O(2^N)

3. 자료구조 연산 비용 더하기
   - Q번 세그트리 쿼리: O(Q log N)
   - N번 정렬 후 Q번 이분 탐색: O(N log N + Q log N)

구현

복잡도별 연산 횟수를 직접 계산해 비교한다.

// 복잡도별 연산 횟수 비교
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n;
  cin >> n;
​
  // floor(log2(n)) 계산
  long long logN = 0, tmp = n;
  while (tmp > 1) { tmp /= 2; logN++; }
​
  cout << "N = " << n << "\n";
  cout << "O(1):       " << 1LL << " ops\n";
  cout << "O(log N):   " << logN << " ops\n";
  cout << "O(N):       " << n << " ops\n";
  cout << "O(N log N): " << n * logN << " ops\n";
  cout << "O(N^2):     " << n * n << " ops\n";
​
  return 0;
}

import math
​
n = int(input())
log_n = int(math.log2(n))
​
print(f"N = {n}")
print(f"O(1):       1 ops")
print(f"O(log N):   {log_n} ops")
print(f"O(N):       {n} ops")
print(f"O(N log N): {n * log_n} ops")
print(f"O(N^2):     {n * n} ops")

import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      long n = Long.parseLong(br.readLine().trim());
​
      // floor(log2(n)) 계산
      long logN = 0, tmp = n;
      while (tmp > 1) { tmp /= 2; logN++; }
​
      System.out.println("N = " + n);
      System.out.println("O(1):       1 ops");
      System.out.println("O(log N):   " + logN + " ops");
      System.out.println("O(N):       " + n + " ops");
      System.out.println("O(N log N): " + (n * logN) + " ops");
      System.out.println("O(N^2):     " + (n * n) + " ops");
  }
}

1000

N = 1000
O(1):       1 ops
O(log N):   9 ops
O(N):       1000 ops
O(N log N): 9000 ops
O(N^2):     1000000 ops

10000

N = 10000
O(1):       1 ops
O(log N):   13 ops
O(N):       10000 ops
O(N log N): 130000 ops
O(N^2):     100000000 ops

함정

BOJ 연습 문제

관련 위키

• 마스터 정리 - 분할 정복 점화식의 복잡도 판정
• 분할 정복 - O(N log N) 알고리즘의 핵심 패턴
• 병합 정렬 - Θ(N log N) 정렬 알고리즘
• 이분 탐색 - O(log N) 탐색
• 정렬 알고리즘 - 복잡도별 정렬 비교
• 자료구조 개요 - 자료구조별 연산 복잡도
• 세그먼트 트리 - O(log N) 구간 쿼리/갱신