배열 메서드의 Big O

push - O(1)
pop - O(1)
shift - O(N)
unshift - O(N)
concat - O(N)
slice - O(N)
splice - O(N)
sort - O(N* log N)
forEach , map, filter , reduce ..etc - O(N)

 

push, pop , shift unshift는 이전 글에서 설명했기 때문에 생략하겠습니다.

concat

concat의 경우에는 여러 배열을 합쳐 줍니다.

결합할 배열이 커질수록, 끝에 붙일 배열의 크기 만큼 시간도 그만큼 늘어나기 때문에 O(N)입니다.

 

slice

slice는 배열의 일부를 가져오거나 전체를 가져올수 있습니다.

엘리먼트 갯수만큼 걸리는 시간이 소요되기 때문에 O(N)입니다.

 

splice

splice는 slice와 달리 엘리먼트를 제거하고 추가합니다.

배열 시작에 추가할수 있고 배열 끝에도 추가할 수 있습니다.

 

배열 중간에 추가한다면 단순하게 O(N)으로 표현합니다.

이렇게 하면 shift를 해서 뒤에 있는 엘리먼트들의 index를 다시 정리해야 합니다.

 

sort

배열을 정렬하는것은 비교를 해야 하고 엘리먼트를 이동해야 하며 정렬하기 위해서는 각 엘리먼트마다 한 번씩 보는 것만으로 충분하지 않습니다. 데이터 수가 2배로 늘면 연산횟수는 2배 넘게 증가되기 때문에 O(n * log N)의 시간 복잡도를 가집니다.

forEach , map, filter , reduce ..etc

엘리먼트마다 한가지 작업을 실행하고, 갯수를 기록하거나 출력을 하거나 boolean으로 확인하는등의 작업을 합니다.

어떤 작업이든 엘리먼트마다 한 작업을 실행합니다.

즉 배열이 커질수록 걸리는 시간도 늘어나기 때문에 O(N)입니다.