TimeSpaceComplexity
시간 복잡도 (Time Complexity)
알고리즘이 문제를 해결하는 데 걸리는 시간을 입력 크기의 함수로 표현
Big-O 표기법을 사용하여 표현
최악의 경우를 기준으로 계산
주요 시간 복잡도
O(1) - 상수 시간
입력 크기와 관계없이 일정한 시간 소요
예: 배열의 인덱스 접근, 해시 테이블 검색
O(log N) - 로그 시간
입력 크기가 커질 때마다 실행 시간이 로그적으로 증가
기본적으로 이진 로그(log₂)를 사용
예: 이분 탐색, 균형 잡힌 이진 트리 검색
로그의 성질:
log₂(8) = 3 (2³ = 8)
log₂(16) = 4 (2⁴ = 16)
log₂(32) = 5 (2⁵ = 32)
O(N) - 선형 시간
입력 크기에 비례하여 실행 시간 증가
예: 배열 순회, 연결 리스트 검색
O(N log N) - 선형 로그 시간
입력 크기와 로그의 곱에 비례하여 실행 시간 증가
예: 퀵 정렬, 병합 정렬, 힙 정렬
N log N의 의미:
N이 8일 때: 8 × log₂(8) = 8 × 3 = 24
N이 16일 때: 16 × log₂(16) = 16 × 4 = 64
N이 32일 때: 32 × log₂(32) = 32 × 5 = 160
O(N²) - 제곱 시간
입력 크기의 제곱에 비례하여 실행 시간 증가
예: 버블 정렬, 선택 정렬, 삽입 정렬
O(2^N) - 지수 시간
입력 크기에 대해 지수적으로 실행 시간 증가
예: 피보나치 수열 재귀 구현
공간 복잡도 (Space Complexity)
알고리즘이 문제를 해결하는 데 필요한 메모리 공간을 입력 크기의 함수로 표현
Big-O 표기법을 사용하여 표현
추가 메모리 공간만을 고려
주요 공간 복잡도
O(1) - 상수 공간
입력 크기와 관계없이 일정한 메모리 사용
예: 단일 변수 사용
O(N) - 선형 공간
입력 크기에 비례하여 메모리 사용
예: 배열, 연결 리스트
O(N²) - 제곱 공간
입력 크기의 제곱에 비례하여 메모리 사용
예: 2차원 배열
복잡도 표기법
Big-O (O) - 최악의 경우
알고리즘의 상한선을 나타냄
예: O(N²)는 최악의 경우 N² 시간이 걸림
Big-Omega (Ω) - 최선의 경우
알고리즘의 하한선을 나타냄
예: Ω(1)은 최선의 경우 상수 시간이 걸림
Big-Theta (Θ) - 평균의 경우
알고리즘의 정확한 성능을 나타냄
예: Θ(N log N)은 평균적으로 N log N 시간이 걸림
Little-o (o) - 점근적 상한
Big-O보다 더 엄격한 상한
예: o(N²)는 N²보다 느리게 증가하지 않음
Little-omega (ω) - 점근적 하한
Big-Omega보다 더 엄격한 하한
예: ω(1)은 상수 시간보다 빠르게 증가
복잡도 계산 시 주의사항
상수는 무시
O(2N) → O(N)
O(N + 1000) → O(N)
가장 큰 항만 고려
O(N² + N) → O(N²)
O(N + log N) → O(N)
중첩된 반복문은 곱하기
이중 반복문: O(N²)
삼중 반복문: O(N³)
실제 적용 예시
// O(N) 시간, O(1) 공간
public static int findMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// O(N²) 시간, O(1) 공간
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}복잡도 최적화 팁
불필요한 반복문 제거
적절한 자료구조 선택
메모이제이션 활용
분할 정복 기법 적용
동적 프로그래밍 고려
Last updated