Skip to content

COMPLEXITY_REFERENCE.md

Latest commit

 

History

History
300 lines (222 loc) · 10.4 KB

COMPLEXITY_REFERENCE.md

File metadata and controls

300 lines (222 loc) · 10.4 KB

시간/공간 복잡도 참고 자료

이 문서는 알고리즘 문제 해결 시 시간 복잡도와 공간 복잡도를 평가하는 데 필요한 참고 자료를 정리합니다.

📊 시간 복잡도 평가 기준

일반적인 경험칙

대부분의 온라인 저지(백준, 프로그래머스 등)에서:

  • 1초에 약 10⁸번(1억 번)의 연산을 처리할 수 있다고 가정합니다
  • 이는 C++/Java 기준이며, Python은 더 느립니다 (약 10배)

시간 복잡도별 안전한 N의 크기 (1초 기준)

시간 복잡도 안전한 N의 크기 이유
O(1) 제한 없음 상수 시간
O(log N) 제한 없음 로그 시간
O(N) N ≤ 10⁸ 10⁸번 연산 = 약 1초
O(N log N) N ≤ 10⁶ 10⁶ × 20 ≈ 2×10⁷ < 10⁸
O(N²) N ≤ 10⁴ (10⁴)² = 10⁸
O(N³) N ≤ 500 500³ = 1.25×10⁸ ≈ 10⁸
O(2^N) N ≤ 20 2²⁰ ≈ 10⁶
O(N!) N ≤ 10 10! = 3,628,800

실제 연산 횟수 계산 예시

N = 10³일 때:

  • O(N) = 10³
  • O(N log N) = 10³ × 10 ≈ 10⁴
  • O(N²) = (10³)² = 10⁶
  • O(N³) = (10³)³ = 10⁹

N = 10⁴일 때:

  • O(N) = 10⁴
  • O(N log N) = 10⁴ × 14 ≈ 1.4×10⁵
  • O(N²) = (10⁴)² = 10⁸
  • O(N³) = (10⁴)³ = 10¹² (시간 초과)

💾 공간 복잡도 평가 기준

Java 자료형별 메모리 사용량

자료형 크기 설명
byte 1 byte -128 ~ 127
short 2 bytes -32,768 ~ 32,767
int 4 bytes -2³¹ ~ 2³¹-1
long 8 bytes -2⁶³ ~ 2⁶³-1
float 4 bytes 단정밀도 부동소수점
double 8 bytes 배정밀도 부동소수점
boolean 1 byte true/false
char 2 bytes 유니코드 문자

Java 자료구조별 메모리 사용량 (추정)

자료구조 요소당 메모리 설명
int[] 4 bytes 기본 배열
long[] 8 bytes 기본 배열
ArrayList<Integer> 약 16 bytes 객체 오버헤드 포함
ArrayList<Long> 약 24 bytes 객체 오버헤드 포함
HashSet<Integer> 약 20 bytes 해시 테이블 오버헤드 포함
HashSet<Long> 약 24 bytes 해시 테이블 오버헤드 포함
HashMap<K, V> 약 32 bytes 키-값 쌍 + 해시 테이블 오버헤드
String 약 40 bytes + 문자 수 × 2 객체 헤더 + 문자 배열

참고: Java는 객체 지향 언어이므로 기본 타입 배열보다 객체 컬렉션이 더 많은 메모리를 사용합니다.

공간 복잡도별 안전한 N의 크기

일반적인 메모리 제한 기준:

  • 128 MB: 백준 온라인 저지에서 가장 흔한 메모리 제한
  • 256 MB: 더 큰 문제에서 사용
  • 512 MB: 매우 큰 문제에서 사용
  • 문제마다 다를 수 있으므로 항상 문제의 메모리 제한을 확인해야 함

128 MB 기준 (가장 일반적):

공간 복잡도 안전한 N의 크기 이유
O(1) 제한 없음 상수 공간
O(N) N ≤ 10⁷ 10⁷ × 8 bytes = 80 MB < 128 MB
O(N log N) N ≤ 10⁶ 10⁶ × 8 bytes × log(10⁶) ≈ 160 MB (경계)
O(N²) N ≤ 10³ (10³)² × 24 bytes = 24 MB < 128 MB
O(N³) N ≤ 200 200³ × 24 bytes ≈ 192 MB > 128 MB

256 MB 기준:

공간 복잡도 안전한 N의 크기 이유
O(N) N ≤ 2×10⁷ 2×10⁷ × 8 bytes = 160 MB < 256 MB
O(N log N) N ≤ 2×10⁶ 2×10⁶ × 8 bytes × log(2×10⁶) ≈ 320 MB (경계)
O(N²) N ≤ 3×10³ (3×10³)² × 24 bytes = 216 MB < 256 MB
O(N³) N ≤ 300 300³ × 24 bytes ≈ 648 MB > 256 MB

512 MB 기준:

공간 복잡도 안전한 N의 크기 이유
O(N) N ≤ 5×10⁷ 5×10⁷ × 8 bytes = 400 MB < 512 MB
O(N log N) N ≤ 5×10⁶ 5×10⁶ × 8 bytes × log(5×10⁶) ≈ 800 MB (경계)
O(N²) N ≤ 4×10³ (4×10³)² × 24 bytes = 384 MB < 512 MB
O(N³) N ≤ 400 400³ × 24 bytes ≈ 1.5 GB > 512 MB

실제 메모리 사용량 계산 예시

N = 10³일 때:

  • int[]: 10³ × 4 bytes = 4 KB
  • long[]: 10³ × 8 bytes = 8 KB
  • HashSet<Long> (N²개): (10³)² × 24 bytes = 24 MB

N = 10⁴일 때:

  • int[]: 10⁴ × 4 bytes = 40 KB
  • long[]: 10⁴ × 8 bytes = 80 KB
  • HashSet<Long> (N²개): (10⁴)² × 24 bytes = 2.4 GB (메모리 초과)

🔍 자료구조별 시간 복잡도

배열 (Array)

연산 시간 복잡도 설명
접근 (arr[i]) O(1) 인덱스로 직접 접근
검색 O(N) 선형 탐색
삽입/삭제 (끝) O(1) 마지막 요소
삽입/삭제 (중간) O(N) 요소 이동 필요
정렬 O(N log N) 최적 정렬 알고리즘

ArrayList

연산 시간 복잡도 설명
접근 (get(i)) O(1) 인덱스로 직접 접근
검색 (indexOf) O(N) 선형 탐색
삽입/삭제 (끝) O(1) 평균적으로
삽입/삭제 (중간) O(N) 요소 이동 필요
contains O(N) 선형 탐색

HashSet

연산 시간 복잡도 설명
추가 (add) O(1) 평균, 최악 O(N)
삭제 (remove) O(1) 평균, 최악 O(N)
검색 (contains) O(1) 평균, 최악 O(N)
크기 (size) O(1) 상수 시간

HashMap

연산 시간 복잡도 설명
추가/수정 (put) O(1) 평균, 최악 O(N)
삭제 (remove) O(1) 평균, 최악 O(N)
검색 (get) O(1) 평균, 최악 O(N)
키 존재 확인 (containsKey) O(1) 평균, 최악 O(N)

PriorityQueue (Heap)

연산 시간 복잡도 설명
추가 (add/offer) O(log N) 힙 구조 유지
최소/최대값 (peek) O(1) 루트 노드 접근
삭제 (poll) O(log N) 힙 구조 유지
검색 O(N) 선형 탐색

LinkedList

연산 시간 복잡도 설명
접근 (get(i)) O(N) 순차 탐색
검색 O(N) 선형 탐색
삽입/삭제 (시작) O(1) 헤드 노드
삽입/삭제 (중간) O(N) 위치 찾기 + O(1)
삽입/삭제 (끝) O(1) 테일 노드 (이중 연결 리스트)

🧮 알고리즘별 시간/공간 복잡도

정렬 알고리즘

알고리즘 최선 평균 최악 공간 안정성
버블 정렬 O(N²) O(N²) O(N²) O(1) 안정
선택 정렬 O(N²) O(N²) O(N²) O(1) 불안정
삽입 정렬 O(N) O(N²) O(N²) O(1) 안정
병합 정렬 O(N log N) O(N log N) O(N log N) O(N) 안정
퀵 정렬 O(N log N) O(N log N) O(N²) O(log N) 불안정
힙 정렬 O(N log N) O(N log N) O(N log N) O(1) 불안정
계수 정렬 O(N + K) O(N + K) O(N + K) O(N + K) 안정

K: 데이터의 범위

그래프 알고리즘

알고리즘 시간 복잡도 공간 복잡도 설명
BFS O(V + E) O(V) 인접 리스트
DFS O(V + E) O(V) 인접 리스트
다익스트라 (우선순위 큐) O((V + E) log V) O(V) 인접 리스트
플로이드-워셜 O(V³) O(V²) 모든 쌍 최단 경로
위상 정렬 O(V + E) O(V) DAG 정렬

V: 정점 수, E: 간선 수

탐색 알고리즘

알고리즘 시간 복잡도 공간 복잡도 설명
선형 탐색 O(N) O(1) 순차 탐색
이진 탐색 O(log N) O(1) 정렬된 배열
깊이 우선 탐색 (DFS) O(V + E) O(V) 그래프
너비 우선 탐색 (BFS) O(V + E) O(V) 그래프

동적 계획법 (DP)

패턴 시간 복잡도 공간 복잡도 설명
1차원 DP O(N) O(N) dp[i]
2차원 DP O(N × M) O(N × M) dp[i][j]
배낭 문제 O(N × W) O(N × W) N: 물건 수, W: 용량
TSP (비트마스크) O(N² × 2^N) O(N × 2^N) N ≤ 16

📐 복잡도 평가 사고 과정

시간 복잡도 평가 단계

  1. 알고리즘의 주요 연산 파악

    • 반복문의 중첩 횟수
    • 재귀 호출의 깊이와 횟수
    • 자료구조 연산의 복잡도

  2. 실제 연산 횟수 계산

    • N의 값에 따른 실제 계산
    • 예: N = 10³일 때, O(N²) = (10³)² = 10⁶

  3. 시간 제한과 비교

    • 연산 횟수 / 10⁸ = 예상 시간(초)
    • 시간 제한 내 통과 여부 판단

  4. 최악의 경우 고려

    • 최악의 경우에도 시간 제한 내 통과하는지 확인

공간 복잡도 평가 단계

  1. 각 자료구조의 메모리 사용량 파악

    • 배열, 리스트, 해시셋 등
    • 요소 개수와 요소당 메모리 크기

  2. 실제 메모리 사용량 계산

    • 자료구조별 메모리 사용량 합산
    • 예: HashSet (N²개) = N² × 24 bytes

  3. 메모리 제한과 비교

    • 사용 메모리 / 메모리 제한 = 사용률
    • 메모리 제한 내 통과 여부 판단

  4. 최악의 경우 고려

    • 최악의 경우에도 메모리 제한 내 통과하는지 확인

⚠️ 주의사항

언어별 차이

  • C++: 가장 빠르고 메모리 효율적
  • Java: 객체 오버헤드로 메모리 사용량이 큼 (약 2-3배)
  • Python: 매우 느림 (약 10배), 메모리도 많이 사용

실제 성능에 영향을 주는 요소

  1. 입출력 시간: 큰 입력의 경우 입출력 시간도 고려
  2. 컴파일러 최적화: 최적화에 따라 실제 속도가 달라질 수 있음
  3. 캐시 효율성: 메모리 접근 패턴에 따라 성능 차이 발생
  4. 연산의 종류: 단순 덧셈 vs 복잡한 연산 (나눗셈, 제곱근 등)

실전 팁

  1. 여유를 두고 계산: 이론적 계산보다 여유있게 평가
  2. 최악의 경우 고려: 평균이 아닌 최악의 경우를 기준으로
  3. 실제 테스트: 가능하면 실제로 테스트해보기
  4. 시간 복잡도 우선: 보통 시간 제한이 공간 제한보다 더 엄격함

📚 참고

  • 각 알고리즘별 상세 설명은 해당 알고리즘 문서를 참고하세요
  • 문제별 복잡도 평가 예시는 각 문제의 2.algorithm.md를 참고하세요