배열의 빅오(Big o)

1. 배열은 객체와 다르게 데이터가 정렬되어 있다.

2. 정렬되어 있는 것이 필요하다면 유용하지만 연산을 하는 시간이 조금 더 걸린다.

추가 - O(N) || O(1)
제거 - O(N) || O(1)
검색 - O(N)
접근 - O(1)

접근

접근은 객체와 동일한 O(1)이며, 추가와 제거는 유동적입니다.

배열 추가와 제거

 

const 예시 = ['코딩','자바스크립트','자료구조']

// 코딩 = 0 , 자바스크립트 = 1, 자료구조 = 2

배열은 각 엘리먼트마다 붙어 있는 index가 존재합니다.

 

예시에서 새로운 값을 push 한다면 객체와 다를것이 없는 O(1) 작업으로 상수 시간입니다.

코딩 = 0 , 자바스크립트 = 1, 자료구조 = 2의 인덱스 값의 변화 없이 새로운 값 = 3으로 생성됩니다.

 

문제가 되는 것은 배열 앞에 추가할 때입니다.

그 이유는 index 때문입니다.

 

새로운 값을 앞에다가 추가한다면, 기존 인덱스들의 값이 변합니다.

'코딩'의 index는 1 '자바스크립트'의 index는 2 이런 식으로 밀려나게 됩니다.

 

크기가 작은 배열에서는 큰 문제가 되지 않겠지만 수천, 수만 개의 값이 존재한다면 새롭게 인덱스를 배정하는 것이 쉽지 않습니다.

배열 앞에 추가한다면 각 엘리먼트마다 작업이 필요하기 때문에  O(N) 선형의 시간을 가지게 됩니다.

 

삭제 또한 같은 이유로 앞에 값을 삭제한다면 O(N) 선형의 시간을 갖습니다.

 

결과적으로 빈 배열 일 경우를 제외하고는 push와 pop이 shift와 unshift보다 빠릅니다.

검색

예시에 1000개의 값이 있고 그중에 '코딩'이란 값이 있는지 확인하고 싶다면 모든 엘리먼트들을 확인해야 할수도 있습니다.

배열의 크기가 커질수록 탐색하는 시간이 길어지기 때문에 O(N) 선형의 시간입니다.