포스팅 목적
위 포스팅에서 알아본 JavaScript 내장 배열 메소드들의 시간 복잡도, 그리고 이와 관련이 있는 JavaScript 배열의 특징까지 알아봅니다.
시간 복잡도
- 초기화
fill, splice : O(n) - 요소 추가 / 제거
pop / push : O(1)
shift / unshift : O(n) - 정렬
sort : O(n log n)reverse - 순회
forEach, map, reduce, reduceRight : O(n) - 조건 판단
every, some, includes, filter : O(n) - 요소 찾기
find / findIndex, indexOf / lastIndexOf : O(n) - 문자열 반환
join, toString - 새로운 배열 생성
concat
slice : O(n)
대체로 배열 메소드의 경우 배열을 완전 탐색하기 때문에 몇 가지를 제외하고는 O(n) 의 시간복잡도를 가지고 있습니다. pop 과 push 의 경우에는 배열의 요소에 접근하는 시간 복잡도가 O(1) 이며, shift 와 unshift 의 경우 모든 배열의 요소를 하나씩 밀어야 하기 때문에 O(n) 의 시간이 걸리게 됩니다.
JavaScript 배열의 특징
엄밀히 말하자면 JavaScript 의 배열은 배열이 아닌 객체입니다. 각각의 메모리 공간이 동일한 크기를 갖지 않아도 되며 연속적으로 이어져 있지 않을 수도 있는 희소 배열입니다. 해시 테이블로 구현된 객체이기 때문에 인덱스로 요소에 접근하는 경우 느리고, 삽입 / 삭제시 더 빠릅니다.
그렇다면 shift(), unshift() 메소드의 시간 복잡도는 O(n) 보다 빠르고, arr[index] 접근의 시간 복잡도가 O(1) 보다 느리다는 거니까 위에 나온 시간 복잡도가 틀리다는 말인데...
우선은 이 정도까지만 알아보겠습니다.
참고 자료
- 자바스크립트 Array 메소드 및 예제에 대한 시간 복잡도 Big O
- 배열과 객체의 성능 분석 (Big O)
- [JS] 📚 배열 💯 이론 + 특징 총정리
- [JavaScript] 배열이 배열이 아니라고?
'자료구조와 알고리즘' 카테고리의 다른 글
| [알고리즘] 이진 탐색 ( Binary Search ) (0) | 2022.01.09 |
|---|---|
| [알고리즘] 완전 탐색 (0) | 2021.12.12 |