배열과 Map/Set의 시간 복잡도를 비교해보자.
1. array
- 접근 (index 활용) : O(1)
- 끝에서부터 삽입, 제거 : O(1)
.push(), .pop()
- 시작에서부터 삽입 제거 : O(n)
.shift(), unshift()
그래서 stack 같은걸 구현할 때 shift, unshift를 쓰면 시간 초과로 틀리고, push, pop쓰면 풀리는 경우가 있었다.
단, shift, unshift처럼 배열의 처음 부분을 조작하는 method가 O(n) 인지, O(1)인지는 언어마다 다르다고 함.
js는 O(n)이다. 첫 번째 요소를 제거/삭제하면, 뒤에 있는 요소들도 전부 하나씩 당기거나 밀어줘야 한다.
2. Map, Set, Object(dictionary)
객체의 한 타입이라고 생각하면 된다. 실제로 typeof 출력해보면 object라고 나옴.
해시를 사용하므로 값 탐색, 추가, 접근, 제거 모두 O(1)의 시간 복잡도를 가진다.
'Algorithm' 카테고리의 다른 글
백준 14425 (nodejs) (1) | 2023.10.23 |
---|---|
[nodejs] for (0) | 2023.08.22 |
Study - Set (0) | 2023.08.17 |
Study - Map (0) | 2023.08.17 |
백준 10815 (nodejs) (0) | 2023.08.17 |