Object와 Array 성능 평가

[JavaScript 알고리즘 & 자료구조 마스터클래스](JavaScript (JS) Algorithms and Data Structures Masterclass) 강의를 듣고 정리한 내용입니다.

1. Object

---

• 특징: 정렬되어 있지 않고 빠른 접근, 추가, 삭제, 수정이 가능합니다.
  • 접근, 추가, 삭제, 수정: O(1)
  • 조회: O(N)

여기서 접근과 조회의 차이가 뭘까요?

const object = { a: "A"};

object.a; // 접근
Object.values(object).find(value => value === "A"); // 조회

접근은 Object를 기준으로 알고 싶은 값의 key를 알고 있을 때 key를 통해 value에 접근하는 상황입니다.
조회는 key를 모를 때, 어떤 값이 있는지 찾기 위해 전체를 순회하며 value를 찾는 과정을 거칩니다.

1.1. Object Method

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

keys, values, entries는 모두 객체 안에 저장된 값이 많아질 수록 증가하기 때문에 선형 시간을 갖습니다.

• Object.hasOwnProperty(): O(1)

hansOwnProperty가 왜 상수 시간을 갖는지 의아할 수 있는데요.
위에서 접근은 상수 시간을 갖는 것처럼 hasOwnProperty는 key를 통해 접근 가능한 값이 있으면 true, 없으면 false를 반환하는 메서드이기 때문에 상수 시간을 갖습니다.

나중에 해쉬 테이블과 해쉬 맵에 대해서 알게 되면 더 자세하게 알 수 있습니다.

2. Array

---

• Array는 정렬된 데이터 구조가 필요할 때 사용합니다.
• 성능 최적화를 위해서는 싱글 리스트와 더블 링크 리스트처럼 선형 리스트 구조가 작업에 따라 배열보다 더 빠를 수 있습니다.
• 특히 배열은 추가, 삭제는 상황에 따라 성능이 좋지 않습니다.
  • 접근: O(1)
  • 추가, 삭제: 상황에 따라 다름
  • 탐색: O(N)

2.1. Array의 추가, 삭제

Array의 추가, 삭제는 상황에 따라 다른 시간 복잡도를 가지는데요.
배열의 끝 지점에 추가, 삭제를 한다면 O(1)의 상수 시간을 갖습니다.

배열 ["가", "나", "다"]가 있다면 위의 그림처럼 0, 1, 2의 인덱스를 갖습니다.

배열의 끝에 ”라”라는 값을 추가한다면, 값을 추가하고 다음 인덱스를 할당하기만 하면 됩니다.
기존 배열 요소들은 영향을 받지 않기 때문에 상수 시간을 갖게 되는 겁니다.

하지만 배열의 시작에 요소를 추가한다면 어떨까요?

배열의 시작에 요소를 추가하게 되면, 기존 배열 요소 모두에게 영향을 미칩니다.
모든 요소의 인덱스를 수정해야 하기 때문입니다.
따라서 배열의 시작에 요소를 추가하면 O(N)이라는 선형 시간을 갖습니다.
삭제도 동일합니다.

따라서 배열의 끝에 요소를 추가, 삭제하는 push, pop은 상수 시간을, 시작에 요소를 추가, 삭제하는 shift, unshift는 선형 시간을 갖게 됩니다.

2.2. Array Method

• push, pop: O(1)
• shift, unshift: O(N)
• concat, slice, splice: O(N)
• sort: O(NlogN)
• forEach, map, filter, reduce, …: O(N)

push, pop, shift, unshift의 시간 복잡도는 앞서 알아봤는데요.

concat은 두 배열을 붙여 새로운 배열을 만드는 메서드입니다.
N개의 요소를 갖고 있는 배열과 M개의 요소를 갖고 있는 배열을 합치면 O(N + M)이 되는데, 대략적인 추세만 보기때문에 O(N)이라고 봅니다.

slice는 기존 배열을 잘라 복사한 배열을 만드는 메서드입니다.
50개의 요소를 갖고 있는 배열에 10개를 복사하는 것, 50개를 복사하는 시간은 모두 복사하는 요소의 갯수만큼 증가하기 때문에 O(N)의 시간 복잡도를 갖습니다.

splice는 기존 배열에 요소를 추가하거나, 삭제하는 작업을 합니다.
배열의 중간 요소를 교체할 수도, 시작에 추가할 수도, 마지막에 추가할 수도 있습니다.
중간 요소들을 이동시켜야 할 수 있기 때문에 일반적으로 O(N)으로 표현합니다.

sort는 O(NlogN)의 시간 복잡도를 갖습니다.
왜냐하면 정렬은 단순히 순회하지 않고, 값을 비교하고 요소를 바꾸는 복잡한 작업을 수행하기 때문입니다.
따라서 단순히 순회하는 O(N)의 시간보다는 더 걸리게 됩니다.
추후에 정렬 과정에서 더 자세히 다루겠습니다.

그리고 나머지 forEach, map, filter, reduce 등은 순회하며 요소마다 한 가지 작업을 수행하기 때문에 O(N)의 시간 복잡도를 갖습니다.

3. 정리

---

구조	작업	시간 복잡도
Object	접근	O(1)
Object	조회	O(N)
Array	인덱스로 접근	O(1)
Array	push/pop	O(1)
Array	shift/unshift	O(N)
Array	탐색(map/filter 등)	O(N)
Array	정렬(sort)	O(NlogN)

• Object는 정렬되어 있지 않지만, 거의 모든 작업을 빠르게 수행합니다.
• Array는 정렬되어 있고, 시작에 요소를 추가, 삭제하는 것보다 마지막에 요소를 추가, 삭제하는 것이 더 빠릅니다.
• 추후에 공부할 링크드 리스트는 시작에 요소를 추가, 삭제해도 상수 시간을 갖습니다.