배열과 객체의 Big O

1. Objects

Big O of Objects

객체는 정렬이 되어 있지는 않지만 입력, 제거, 접근이 매우 빠르다.
-> 정렬이 중요하지 않을 때 객체는 좋은 선택지가 될 수 있다.

• Insertion, Removal, Access : O(1)
• Searching : O(n)

Big O of Object Methods

• Object.keys : O(n)
• Object.values : O(n)
• Object.entries : O(n)
• hasOwnProperty : O(1)
  (탐색이 아니라 key로 접근하는 것이기 때문에 constant함.)

2. Arrays

Big O of Arrays

배열은 정렬이 되어 있지만 입력과 제거의 성능이 좋지 않은 경우가 종종 있다.
(대신 접근은 빠르다.)

• Insertion, Removal : 상황에 따라 다름.
  (push나 pop을 하는 경우에는 단순히 O(1)이지만, shift나 unshift를 하는 경우에는 뒤에 있는 index가 다 바뀌기 때문에 O(n)이 된다. 따라서 push/pop이 shift/unshift보다 작업시간이 더 빠르다. 이렇듯 배열 앞 부분에 작업을 하면 시간이 오래 걸리기 때문에 피하는 것이 좋다.)
• Searching : O(n)
• Access : O(1)

Big O of Array Methods

• push, pop : O(1)
• shift,unshift : O(n)
• concat, slice, splice, forEach, map, filter, reduce etc.. : O(n)
• sort : O(n * log n)
  (가장 오래 걸림)