[JS 알고리즘&자료구조] Big O 배열 메소드

아래는 각각의 배열 메소드에 대한 Big O 표기법이다.

push // O(1), 배열의 끝에 단순히 데이터와 인덱스를 추가
pop // O(1), 배열의 끝에 있는 데이터와 인덱스를 삭제
shift // O(N), 배열의 시작에 데이터를 추가하므로 뒤에 있는 데이터들의 인덱스 전부 수정
unshift // O(N), 배열의 시작에 있는 데이터를 삭제하므로 뒤에 있는 데이터들의 인덱스 전부 수정
concat // O(N), 두 개의 배열을 합친 다른 배열을 만듬 (배열들의 데이터들을 다른 배열로 복사)
slice // O(N), 배열 일부 혹은 전체를 가져옴 (10개든 100개든 복사하는 것이므로) 
splice // O(N), 배열 시작, 중간 혹은 끝에 데이터를 추가

위에 언급된 메소드들 외에도 일반적으로 배열의 메소드들은 O(N)이라고 보면 된다. 하지만 아래의 메소드는 다르다.

sort // O(N*log N), 배열을 정렬하는 것은 O(N)보다는 확실히 크다

배열을 정렬하는 것은 많은 일을 해야만 한다. 엘리먼트들끼리 비교를 하고 엘리먼트를 이동하는 등 단순히 엘리먼트를 하나씩 보는 것만으로 충분하지 않다. 당장은 더 자세히 살펴보지는 않겠다.

여기서 객체와 배열에 대한 정리하자면, 객체의 거의 모든 작업들에 있어 빠르게 진행되지만 (상수 시간이 소요됨) 정렬되어 있지는 않고 배열은 정렬되어 있으나 끝에 추가하고 제거하는 작업을 제외하면 나머지 작업들은 시간의 소요가 객체보다는 크다.