02 배열과 객체의 성능 평가

  이번 강의에서는 빅오의 시점에서 객체와 배열이 어떻게 작동되는지, 왜 배열의 앞에 데이터를 추가하는것이 안좋은 것인지, 또 메서드들은 빅오의 관점에서 어떻게 표현되는지 확인해보았다.

 

2.1 객체의 빅오

let instructor = {
    firstName : "mark",
    inInstructor : true,
    favoriteNumbers : [1,2,3,4,5]
};

  우선 객체는 데이터가 정렬되어 있을 필요가 없을때, 빠른 접근, 입력 그리고 제거를 원할 때 좋다. 한마디로 정렬되어 있지는 않지만 그 외의 것들은 처리 속도가 매우 빠르다. 이를 빅오 표기법의 관점에서는 입력,제거,접근은 O(1)의 시간 복잡도를 갖는다. 즉 자바스크립트의 객체는 어떤 정보든 상수 시간안에 저장할 수 있고, 원하는 내용을 상수 시간안에 불러올 수도 있으며 특정 프로퍼티를 상수 시간안에 수정할 수도 있다는 말이다. 그러나 주의해야할 것은 탐색은 O(N)의 시간 복잡도를 갖는다. 프로퍼티 키를 통해 하나 하나 값을 다 확인해야 하기 때문이다. 즉, 데이터의 양이 많으면 많을수록 시간이 오래 걸리므로 O(N)시간 복잡도를 갖는다.

 

2.2 객체 관련 메서드

1. Object.keys - O(N)

  프로퍼티가 늘어나면 늘어 날 수록 나열해야 하는 프로퍼티키가 많아지기 때문이다.

 

2. Object.values - O(N)

  Object.keys와 동일한 이유다.

 

3. Object.entries - O(N)

  Object.keys와 동일한 이유다.

 

4. hasOwnProperty - O(1)

  예를들어 firstName이라는 속성을 전달하면, firstName 속성이 있는지 없는지만 불리언 값으로 반환해주기 때문이다.

 

2.3 배열안의 데이터에 접근이 느린 이유

let names = ['Danny','Jessie','Andy'];

let values = [true, {}, [], 2, "hello"];

  배열의 가장 중요한점을 보자면 정렬이 되어 있다는 것이다. 그러나 연산에 시간이 더 걸릴 수도 있다.(배열은 인덱스를 갖기 때문) 배열의 특정값을 탐색하는 것은 O(N)의 시간 복잡도를 갖는다. 배열안에 특정 값이 있는지 하나 하나 확인해야 하기 때문이다. 그러나 접근은 O(1)의 시간 복잡도를 갖는다. (인덱스를 갖기 때문에 0부터 원하는 값에 도달할 때까지 하나 하나 확인하는 것이 아니다. 인덱스를 통해 바로 찾아 들어갈 수 있다.) 그러나 삽인이나 제거의 경우에는 어디에 위치하는에 따라 시간 복잡도가 달라질 수 있다. 이러한 문제가 생기는 이유는 인덱스가 존재하기 때문이다. 배열의 맨 뒤에 값을 추가하거나 삭제하는것은 O(1)복잡도를 갖겠지만, 값을 배열의 맨 앞이나 중간에 붙이는 경우에는 인덱스를 다 옮겨야 하기 때문에 O(N)복잡도를 갖는다. 

 

2.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(N*log N) 자세한건 후술 예정

9. forEach/map/filter/reduce/etc. - O(N) 요소마다 하나씩 작업을 실행해야 하므로 배열이 커질수록 걸리는 시간도 비례함

 

  여기서 결론적으로 가장 중요한것은 객체는 거의 모든 것을 빠르게 처리하지만, 정렬되어 있지 않다. 배열은 정렬되어 있지만 배열의 끝에 요소를 추가하고 삭제하는것은 빠를지 모르지만 배열의 앞이나 중간에 요소를 추가하고 제거하는 시간은 연산의 횟수에 비례해 증가한다는 것이다.(인덱스 때문에)