Study - Array vs. Map/Set

배열과 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)의 시간 복잡도를 가진다.