Big-O로 보는 자바스크립트의 Object와 Array

왜 알아야 할까

우리가 너무 익숙하게 사용하는 객체와 배열의 메서드를 사용할 때마다

어떤 복잡도를 갖는지를 알아야 계산이 가능하기 때문이다.

 

for문 안에서 만약 배열을 slice 하거나 index를 찾기위해 indexOf 와 같은 메서드를 사용하는 경우

순식간에 복잡도는 O(n^2) 가 되어버리기 때문에 ,, 항상 하나를 사용하더라도 주의해서 사용해야 한다.

 

Object 

키와 값으로 이루어진 자바스크립트의 객체

const person = {
	firstName: 'yy';
    lastName: 'k';
}

 

insert : O(1)

remove : O(1)

access : O(1)

search : O(n) -> 최악의 경우에는 모든 요소를 다 돌아야 찾을 수 있기 때문!

Object.keys() : O(n)

Object.values() : O(n)

Object.entries() : O(n)

 

Array

인덱스를 통해서 정렬된 값들의 컬렉션

const odd = [1, 3, 5, 7, 9];

 

- 가장 끝에 값을 생성하거나 삭제할 때 : O(1)

-가장 앞에 값을 생성하거나 삭제할 때 : O(n)

  가장 앞에 값을 생성하고 그 뒤에 있는 배열의 인덱스를 다 앞으로 당기거나 뒤로 미루어야 하기 때문에!

access : O(1)

search : O(n)

push / pop : O(1)

shift / unshift / concat / slice / splice : O(n)

forEach / map / filter / reduce : O(n)