[BigO] 객체와 배열

1. 객체

빠른접근, 빠른제거에 좋다

정렬되어있지는 않지만 다른건 매우 빨드ㅏ.

(1) Insertion(추가) : O(1)

(2) Removal(제거) : O(1)

(3) Searching(탐색) : O(N)

(4) Access(접근) : O(1)

객체의 입력,제거,접근은 다 상수시간이다. 탐색은 n의 시간복잡도를 가진다.

 

2. 객체 메서드들

(1) Object.keys : O(N)

(2) Object.values : O(N)

(3) Object.entries : O(N)

(4) hasOwnProperty : O(1)

 

3. 배열

객체와의 가장 큰 차이는 정렬을 할 수 있다는 것이다.

(1) Insertion(추가) : It depends(상황에 따라)

(2) Removal(제거) : It depends(상황에 따라)

(3) Searching(탐색) : O(N)

(4) Access(접근) : O(1)

배열이 얼마나 긴지는 중요하지 않고 접근은 상수시간이다.

 

배열의 끝에 값을 추가하는 경우는 O(1)

하지만 배열의 앞에 추가하는 경우에는 각 요소들의 인덱스값도 바꿔줘야 하기 때문에 O(N)이 된다.

제거하는 경우에도 마찬가지 이다.

=> 배열앞에 추가하고 제거하는것은 시간이 오래 걸린다.

=> 비어있는 배열을 제외하고 push pop 이 shift unshift 보다 속도가 더 빠르다.

 

4. 배열 메서드들

(1) push : O(1)

(2) pop : O(1)

(3) shift : O(N)

(4) unshift : O(N)

(5) concat : O(N)

(6) slice : O(N)

(7) splice : O(N)
(8) sort : O(NlogN)

  - sort는 정렬를 할때 조건이 또한번 붙기 때문에 다른 메서드들 보다 좀더 오래 걸린다.

(9) forEach/map/filter/reduce/etc : O(N)

 

5. 객체와 배열의 차이점

객체는 거의 모든것을 더 빠르게 하지만 정렬되어 있지 않고

배열은 정렬되어 있지만 끝에 추가하고 제거하는 작업이 

시작에 추가하고 제거하는 작업보다 훨씬 빠르다.