[Javascript/JS] 자바스크립트에서의 배열과 시간복잡도

이번 포스팅은 Javascript의 배열에서 자주쓰이는 함수들의 시간복잡도를 알아보려고 합니다.

배열은 정말 많이 쓰이는 자료구조 입니다. 그만큼 잘못사용한다면 성능에 영향을 끼칠 수 있습니다.

Javascript에서의 배열 함수들의 실행 구조와 시간복잡도에 대해서 알아보겠습니다.

---

! 우선 Javascript에서의 배열은 저희가 알고 있던 배열과는 조금 다릅니다.

일반적인 배열이라는 자료구조는 동일한 크기의 메모리 공간이 연속적으로 나열된 자료구조입니다..

하나의 타입을 갖고 연속적으로 인접해 있는 상태입니다.

address(메모리 주소)	1000	1008	1016	1024
array	10	20	30	40
index	0	1	2	3

이러한 배열을 dense array라고 합니다.

이렇게 생긴 형태의 배열은 index로 단번에 요소에 접근하여 시간복잡도O(1)이라고 할 수있고 빠릅니다.

또한 배열을 한 번 순회하거나, 특정한 값을 찾기 위해 탐색하는 경우 발견할 때 까지 확인해야 하므로 O(n)에 시간복잡도를 갖습니다.

가장 불편한 점은 요소의 삽입과 삭제입니다.

중간에 요소를 삽입, 삭제 해야한다면 해당 index부터 끝까지의 요소를 뒤로 한칸씩 미루는 공사를 해야합니다.

 

! Javascript에서의 배열은 어떨까요?

Javascript에서의 배열은 하나의 타입이 아니어도 되며, 연속적으로 이어져 있지 않은 sparse array입니다. 엄밀히 말하면 객체라고 볼 수 있습니다.

 

Javascript에서의 배열 

다음과 같이 index를 key로 가지며 length 를 갖는 특수한 객체입니다.

그렇기 때문에 다양한 형태의 타입들이 하나의 배열에 들어 가 있을 수 있죠.

 

이러한 JS의 배열은 어떠한 장단점을 갖을까요?

●장점

    -요소의 삽입 삭제가 효율적이다.

    -다양한 자료구조를 담을 수 있다.

    - ...

◆단점

    -요소의 접근이 해시테이블의 형태이기에 직접접근 보다 느리다. -> 모던 자바스크립트 엔진은 이를 어느정도 

     해결했다고 합니다.

    -배열 요소를 사용할 때 타입을 잘못인지하여 오류를 발생시킬 수 있다.

    - ...

 

 

---

그렇다면 이제 몇 가지의 간단한 배열 관련 함수들의 시간복잡도를 알아보겠습니다.

 

① push && pop

단순히 배열의 맨 끝에 요소를 추가, 삭제 하는 함수입니다.

순회할 필요도 없으며 시간복잡도는 O(1)입니다.

 

② unshift && splice

unshift와 splice는 배열의 맨 앞과 중간에 요소를 추가하는 함수입니다.

따라서 기존의 index들이 바뀌어야 하므로 1회 순회를 하며 작업하게 됩니다. O(n)

 

③ sort

이는 구현 방식에 따라 속도와 복잡도가 달라질 수 있습니다.

(arr.sort()는 ASCII 를 기준으로 정렬하기에 생각과 다른 결과가 나올 수 있습니다. )

 

④ filter && map && forEach 

O(n)의 시간복잡도를 갖습니다. 하지만 안에서 2중으로 사용하게 되면 O(n^2)이 되고 ... 그 후는...

(forEach vs for 문 단순 시간차이는 일반적으로 for문이 약 1.4배 빠르다고 합니다. 성능을 위해선 for문을 이용하는 방법이 있겠네요)

(ArrayList, LinkedList, Array 에서의 차이를 확인하려면 siyoon210.tistory.com/99 참고하시면 좋을 것 같습니다)

 

 

이상으로 Javascript의 배열에 대해 얕게나마 알아봤습니다.

다른 언어의 배열을 사용하다 JS를 사용하게되고 처음엔 되게 낯설어서 어버버했었는데 사용하다보니

훨씬 편한느낌이긴 하네요.

 

읽어주셔서 감사합니다. 틀린점이나 보완해야할 점이 있다면 말씀주시면 정말 감사하겠습니다.