[JavaScript] 배열과 시간복잡도
JavaScript에서의 배열은 일반적으로 알고있는 배열과는 다르다.
일반적인 배열이라는 자료구조는 동일한 크기의 메모리 공간이 연속적으로 나열된 자료구조이다.
| address | 1004 | 1008 | 1012 |
| array | 10 | 20 | 30 |
| index | 0 | 1 | 2 |
이러한 배열을 dense array라고 한다.
이렇게 생긴 형태의 배열은 index로 단번에 요소에 접근하여 시간복잡도 O(1)이라고 할 수 있고 빠르다.
또한 배열을 한 번 순회하거나, 특정한 값을 찾기 위해 탐색하는 경우 발견할 때 까지 확인해야 하므로 O(n)의 시간복잡도를 가진다.
가장 불편한 점은 요소의 삽입과 삭제이다.
중간에 요소를 삽입, 삭제 해야한다면 해당 index부터 끝까지의 요소를 뒤로 한칸씩 미루는 공사를 해야한다.
JavaScript에서의 배열
Jacascript에서의 배열은 정수 시간 키(인덱스)와 특정 배열별 동작을 갖춘 객체로 구현된다.
index를 key로 가지며 length를 갖는 특수한 객체입니다.
장점
- 요소의 삽입 삭제가 효율적이다.
- 다양한 자료구조를 담을 수 있다.
단점
- 요소의 접근이 해시테이블의 형태이기에 직접접근 보다 느리다
- 배열 요소를 사용할 때 타입을 잘못 인지하여 오류를 발생시킬 수 있다.
push && pop
단순히 배열의 맨 끝에 요소를 추가, 삭제 하는 함수입니다.
기본적으로는 O(1)이다.
그러나 때때로 기본 동적 배열의 크기 조정(상환)이 있을 수 있고, 이로 인해 경우에 따라 O(n)의 시간복잡도가 발생할 수 있다.(dynamic array의 크기 조정)
unshift && splice
배열의 맨 앞과 중간에 요소를 추가하는 함수이다.
기존의 index들이 바뀌어야 하므로 1회 순회를 하여 작업한다. O(n)
검색(선형검색, indexOf)
정렬되지 않은 배열에서 요소를 검색하려면 선형 검색이 필요하며, 일치하는 항목을 찾거나 배열 끝에 도달할 때까지 각 요소를 확인해야 할 수 있다. 시간복잡도 O(n)
검색(이진검색, log n)
배열을 정렬하면 이진 검색을 사용할 수 있으므로 로그 시간 복잡도가 발생한다. 그러나 Javascript에 내장된 'indexOf' 메소드는 선형 검색을 사용하므로 이진 검색을 수동으로 구현하거나 최적화를 위해 특수 라이브러리를 사용해야 한다.
반복(forEach, map, filter)
배열을 반복하려면 각 요소를 한 번 방문해야 하므로 선형적인 시간 복잡도가 발생한다. 시간복잡도 O(n)