복잡도는 시간 복잡도와 공간 복잡도로 나뉨
시간 복잡도
- 입력 크기(n)에 따라 알고리즘이 실행되는 데 걸리는 시간을 수치적으로 표현한 것
- 반복 횟수를 기준으로 측정하며, Big-O 표기법을 사용
for (int i = 0; i < n; i++) {
System.out.println(i); // O(n)
}📌 시간 복잡도 비교 (증가 속도 순)
| 복잡도 | 설명 |
|---|---|
| O(1) | 상수 시간 (가장 빠름) |
| O(logn) | 로그 시간 |
| O(n) | 선형 시간 |
| O(nlogn) | 병합 정렬 등 |
| O(n²) | 이중 반복문 |
| O(2ⁿ) | 지수 시간 (느림) |
| O(n!) | 순열 등 (매우 느림) |
공간 복잡도
- 알고리즘이 실행될 때 사용하는 메모리 공간의 양을 의미
- 변수, 배열, 재귀 호출 시의 스택 공간 등을 포함
int[] a = new int[1004]; // O(n)자료구조별 시간 복잡도
📌 평균 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열 (Array) | O(1) | O(n) | O(n) | O(n) |
| 스택 (Stack) | O(n) | O(n) | O(1) | O(1) |
| 큐 (Queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 (Hash) | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리 (BST) | O(logn) | O(logn) | O(logn) | O(logn) |
📌 최악의 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 해시 테이블 (충돌 시) | O(n) | O(n) | O(n) | O(n) |
| BST (불균형 트리) | O(n) | O(n) | O(n) | O(n) |
시간 복잡도 → 효율성 판단 기준
공간 복잡도 → 메모리 사용량 판단 기준
좋은 알고리즘은 빠르면서도 공간을 덜 차지하는 구조
참고: 북스터디 - 면접을 위한 CS 전공지식 노트 (Chapter 5-1)
dock 사이즈 다르잖아