배열(Arrays)의 BIgO 성능

배열은 정렬된 자료구조로써 인덱스를 통해 자료들을 배열한다.

 

이 인덱스라는 존재가 배열의 연산성능을 다소 희생시킬 수 있다.

 

객체는 그냥 종이봉다리에 키값쌍을 잔뜩넣은 한 뭉치라

굳이 인덱스에 신경 쓸 필요가 없지만

 

배열은 중간에 자료를 하나 넣으면

그 뒤의 모든 인덱스를 일일히 수정해주어야 한다.

따라서 삽입과 삭제의 경우, 그 연산 위치에 따라 빅오 성능이 달라진다.

 

• 삽입 - 배열끝이냐 처음, 중간이냐에 따라 달라짐
• 삭제 - 배열끝이냐 처음, 중간이냐에 따라 달라짐
• 검색 - O(N)
• 접근 - O(1)

 

만약 배열 끝에 push만 할 경우,

인덱스만 하나 추가하고 자료를 하나 더 붙여주면 되기 때문에

push의 시간은 O(1)이다.

배열의 끝 자료를 삭제하는 pop도 마찬가지이다.

 

배열의 앞에서 자료를 추가, 삭제하는 shift, unshift의 경우

앞에서 추가를 하더라도

뒤의 모든 인덱스를 전부 다 수정해야 하기 때문에

shift와 unshift는 O(N)의 노테이션을 가진다.