Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 유니온파인드
- 트러블슈팅
- DFS
- 부분수열의합2
- BFS
- 기본유형
- 백준
- 그래프
- 싸피
- 완탐
- 알고리즘
- SSAFY
- database
- Java
- 그리디
- 자바
- 코드트리
- JUnit
- 코딩테스트실력진단
- Spring
- JPA
- Union Find
- SWEA
- 다익스트라
- 다시보기
- 알고리즘기본개념
- 코딩테스트
- 완전탐색
- 코테
- DP
Archives
- Today
- Total
HwangHub
공간복잡도 본문
시간복잡도에 비해 소홀해지기 쉬운데, 공간복잡도 또한 최적화하면 좋으므로 알아두도록 하겠습니다.
메모리 계산은 보통 C++ 기준으로 생각하는데, 아래 테이블은 자바의 데이터 타입별 메모리 사용 크기이므로 참고하면 좋을 것 같습니다.
C++의 int는 4byte이며, int로 20,000,000(2천만) 정도가 대략 80MB라는 것을 기준으로 계산하면 편합니다. 마치 시간복잡도 중에서 N이 1억번에 1초로 기준을 잡는 것과 동일합니다.
public static final int N = 20,000,000;
int[] a = new int[N]; // 80 MB
int[] a = new int[N/10]; // 80 / 10 = 8 MB
char[] a = new char[N]; // 80 / 2 = 40 MB
double[] a = new double[N]; // 80 * 2 = 160 MB
이러한 방식을 바탕으로 공간복잡도를 계산할 수 있습니다.
한번 빅오 표기법으로 계산해봅시다.
def solution(n):
list = int[n][n][n]
for i in range(0, n):
tmp = int[n]
for j in range(0, n):
tmp[j] = list[0][i][j]
위 함수에서는 공간복잡도를 빅오표기법으로 계산하면 O(N^3)가 됩니다.
'CS-STUDY > 자료구조 & 알고리즘' 카테고리의 다른 글
우선순위 큐(Priority Queue) (0) | 2023.07.29 |
---|---|
HashMap, TreeMap, HashSet, TreeSet (0) | 2023.07.29 |
시간복잡도 (0) | 2023.07.21 |
코딩테스트 시작 전 유형 익히기 (0) | 2023.07.11 |
[그래프] 인접 행렬, 인접 리스트 (스크랩) (0) | 2023.07.11 |
Comments