[알고리즘] 자바스크립트 객체와 배열의 시간복잡도

* 해당 글은 [Udemy] JavaScript Algorithms and Data Structures Masterclass 강의 일부를 정리한 내용입니다.

 

객체의 빅오

---

1. 객체는 정렬되어 있지않아 빠르다.

 

2. 삽입(insertion), 제거(removal), 접근(access) O(1) 

: 앞과 뒤가 존재하지않고 오직 key로 삽입, 제거, 접근을 수행하므로 상수시간이 소요된다.

 

3. 검색(searching) O(N)

: key를 찾는 것이 아니라 value가 어느 속성에 있는지 하나하나 확인하는 작업. n이 늘어남에 따라 시간이 오래 소요됨. 

 

4. 객체의 메서드 빅오

O(N) : Object.keys, Object.values, Object.entries

O(1) : hasOwnProperty : key를 넘기면 boolean을 반환. access의 개념

 

배열의 빅오

---

1. 배열은 정렬되어있으므로 특정 기능에 대해 객체보다 성능이 떨어질 수 있음.

 

2. 접근(access) O(1) 

: 모든 요소를 훑는 것이 아님. index로 빠르게 접근가능

 

3. 삽입(insertion), 제거(removal)  O(1) 혹은 O(N) 

: 배열의 맨 뒤에 요소를 삽입/제거하는 것은 상수시간이 소요된다. 반면 앞이나 중간에 요소를 삽입/제거하면 그 뒤의 모든 요소들의 인덱스를 재배치해야하므로 N개의 갯수에 따라 시간이 오래 걸리게 됨.

 

4. 검색(searching) O(N)

 

5. 배열의 메서드 빅오

O(1) : push, pop

O(N logN) : sort

O(N) : shift, unshift, slice, splice, concat, forEach, map, filter, reduce etc..