배열 시간복잡도 정리해보기

- arr.splice()

splice 메서드 같은 경우는 삭제하려는 요소의 위치와 배열 개수에 따라서 시간 복잡도가 달라진다.

삭제 하려는 요소가 배열의 맨 끝에 존재 할 경우에는 O(1)의 시간 복잡도이지만,

요소가 중간에 위치할 경우 O(n)의 시간 복잡도를 가진다.

- arr.slice()

배열의 특정 범위를 잘라서 그 범위를 반환한다. 보통 자르는 요소를 k개라 했을때, O(k)의 시간 복잡도를 가진다.

- arr.push()

배열의 맨 끝에 요소를 추가한다. 끝에만 추가하는 것이므로 O(1)의 복잡도를 가진다.

- arr.pop()

배열의 맨 끝 요소를 제거한다. 끝 요소만 제거하므로 O(1)의 시간 복잡도를 가진다.

- arr.unshift()

배열의 시작 부분에 요소를 추가한다. 나머지 배열의 요소를 다 한칸씩 뒤로 밀어야하므로 O(n)의 시간복잡도를 가진다.

- arr.shift()

배열의 시작 부분 요소를 제거한다. 나머지 배열의 요소를 한칸씩 다 앞으로 땡겨와야하므로 O(n)의 시간복잡도를 가진다 .

- arr.concat()

두 배열을 합친다.

O(n+m)이라고 표현하지만 이는 O(n)과 마찬가지이다.

- arr.sort()

배열의 요소들을 정렬한다.

O(n * log(n))의 시간복잡도를 가진다.

O(n * log(n)) 복잡도는 O(n)보다는 높은 시간 복잡도를 가지지만 O(n^2)보다는 낮은 시간 복잡도를 가진다.

- 그 밖에 forEach, map, filter, reduce, some, every 등등 배열 전체를 순회하는 메서드

배열 전체를 순회하므로 O(n)의 시간복잡도를 가진다.