Big O of JavaScript Objects

02·2022년 1월 16일
0

Javascript에서 objectskeys-values쌍은 index가 따로 없기 때문에 삽입, 제거, 탐색, 접근 등의 작업에 드는 시간이 arrays와 다르다.

예를 들어 arrays의 경우, 끝부분이 아닌 곳에 element가 삽입 혹은 제거되면
그 뒤의 모든 elmentsindex가 한 칸 씩 뒤로밀려 재배열되기 때문에 선형 시간(O(n))이 걸리는 데에 반해,
objectskeys-values쌍은 index가 따로 없기 때문에, 즉 순서 자체가 없기 때문에
arrays와 달리 같은 작업을 처리하는 데에 상수 시간(O(1))이 걸린다.
다만 value를 찾아야 하는 작업은 모든 keys를 확인해야하기 때문에 선형 시간이 걸린다.

object methods를 사용할 때에 각 method의 시간 복잡도를 파악해두면 좀 더 효율적인 알고리즘을 작성할 수 있다.

Big O of Obejects

  • Insertion(keys-values 삽입) O(1)

  • Removal(keys-values 제거) O(1)

  • Searching(value 탐색) O(n)

  • Access(key 접근) O(1)

Big O of Obeject Methods

  • keys O(n)

  • values O(n)

  • entries O(n) (keys-values 모두 가져오기 때문에 위 method들에 비해서는 좀 더 시간이 든다.)

  • hasOwnProperty O(1)

profile
코스피 9000 기원, 내 취직도 기원

0개의 댓글