DevSSOM
자료구조 - 배열과 해쉬의 차이 본문
반응형
해쉬
: 식별자(Key)가 있는 데이터, 시간복잡도↓(항상 O(1)) / 공간복잡도↑
배열
: 식별자(Key)가 없는 데이터, 시간복잡도↑(O(N)) / 공간복잡도↓
만약, 시간복잡도를 얻으려면 공간복잡도를 포기하고, 해쉬보다는 배열의 자료구조를 선택해야 효율적인 알고리즘을 짤 수 있음. 이렇게 하나를 얻기위해 하나를 포기해야 한다는 의미로 trade-off라는 말을 씀. 자료구조에서 특히 많이 쓰이는 말.
728x90
반응형
'자료구조' 카테고리의 다른 글
| 자료구조 - 배열 문제 : 틀린 문자 찾기 (0) | 2021.06.18 |
|---|---|
| 자료구조 - 배열 문제 : 세번째로 큰 숫자 찾아내기 (0) | 2021.06.17 |
| 자료구조 - 애너그램 탐지 문제 (0) | 2021.06.17 |
| 자료구조 - 해쉬 (0) | 2021.06.16 |
| 자료구조 - 배열 문제 : 배열의 회전 (0) | 2021.06.15 |
| 자료구조 - 배열 (0) | 2021.06.14 |
| 자료구조 - 배열 문제 : 중복된 수 제거하기 (0) | 2021.06.14 |
댓글