[알고리즘]배열(Array)의 Big O

객체와 달리 배열은 정렬이 되어있다. 정렬되어 있는 것이 필요하다면 유용할지라도

연산을 하는 시간 더 증가할 수 있다. 특히 입력과 제거를 할때 성능이 희생된다.

 

입력(Insertion) - It depends...
제거(Removal) - It depends...
탐색(Searching) - O(N)
접근(Access) - O(1)

 

만약 Array의 3000번째 element를 요청했을때 JavaScript는 모든 element을 거치며 접근하지 않는다.

지름길을 가지고 있다고 생각하면 된다. 그렇기에 배열의 길이는 중요하지 않다. O(1)

 

입력은 정렬되어 있는 것과 관련이 있기에 어디에 입력(추가)하는 지에 달려있다. 

만약 배열의 마지막에 element를 push로 추가한다면 O(1)으로 상수 시간일 것이다.

문제는 배열의 앞쪽에 추가할 때 발생한다. 수천개가 있는 배열이라하면 index를 새로 배정하는 것이 쉽지 않을 것이다.

그렇기 때문에 배열 앞에 추가한다면 element마나 하나씩 작업해야하니 O(N) 선형 시간이다.

 

앞에서 제거하는 것도 마찬가지이다. 배열 앞에 추가하고 제거하는 것은 최대한 피해야한다.

무조건 피하라는 것은 아니며 끝에서 추가하고 제거하는것만큼 효율적이진 않다는 것을 알아야 한다.

비어있는 배열일때만 제외하고는 push와 pop이 shift와 unshift보다 빠르다.

 

탐색은 가장 빨라도 O(N) 선형 시간이다. 정렬되어 있지 않은 상태에서 찾으려는 데이터가 포함되어 있는지 알고싶다면 모든 element를 각각 확인해야할 수 있다. 그만큼 배열의 크기가 커질 수록 탐색 시간이 길어지기에 O(N) 선형 시간이다.

 

 

외울필요 없이 빅오 표기법 관점에서 어떻게 이런 빅오를 가지는 지 이해하고 있으면 된다.

 

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

 

concat같은 경우 여러 배열을 합쳐준다. O(N)이라고 하면 배열 하나에 있는 element의 N개수에 적용하는 작업이라고 생각할 수 있는데 2개라면 어떨까? 물론 걸리는 시간은 사실상 O(N+M)이고 M은 또다른 배열의 크기라고 말할 수 있겠지만 O(N)으로 표현하면 충분하다. 결국 배열이 클수록 끝에 붙일 배열의 크기가 커지니 그만큼 시간도 늘어날 것이다.

 

slice는 배열 일부나 전체를 가져올 수 있다. 걸리는 시간은 복사하는 element의 개수만큼 늘어나게 된다.

얼마나 많은 개수를 복사하는 지가 중요하기에 O(N)이다.

 

splice는 element를 제거하고 추가한다. 배열 시작에 추가할 수 있고 끝에도 추가 할 수 있다. element를 교체할 수도 있다. 일반적으로 O(N)으로 표현한다. 

 

sort에서 주목할 점은 배열을 정렬하는 것은 O(N)보다 더 크다는 것이다.

비교하고, elements를 이동해야하고, elements을 한번씩 보는 것만으로 충분하지 않다.

 

forEach/map/filter/reduce 등 모두 O(N)이다. element마다 한가지 작업을 실행하고 개수를 기록하고, boolean으로 확인하고 출력을 할 수도 있고, 어떤 작업이든 element마다 한 작업을 실행해야 하기에 배열이 커질수록 오래걸린다. O(N)이다.

 

객체는 거의 모든 것을 더 빠르게 하지만 정렬되어 있지 않음.

배열은 정렬되어 있지만, 끝에 추가하고 제거하는 작업이 시작에 추가하고 제거하는 작업보다 훨씬 빠름.