[JS 알고리즘] 배열 및 객체의 성능 분석

Object

특징 : Unordererd , key value pairs

객체를 언제 사용하는가 ?

1. 순서가 필요 없을 때
2. 빠른 접근(삽입, 제거)이 필요할 때

Big O of Objects

• Insertion - O(1)
• Removal - O(1)
• Searching - O(N)
• Access - (O1)

---> 따라서 , 순서가 필요 없을 때 객체는 최고의 선택이다.

객체 메서드의 Big O

• Object.keys - O(N)
• Object.values - O(N)
• Object.entries - O(N)
• hasOwnProperty - O(N)

Array

특징 : Ordered lists

Array를 언제 사용하는가 ?

• 순서가 필요할 때

• 빠른 접근(Access)이 필요할 떄

  • Array의 요소 접근은 항상 빠르지만 , 삽입이나 제거는 상황에 따라 다르다.

• Big O of Arrays

  • Insertion - 상황에 따라 가변
  • Removal - 상황에 따라 가변
  • Searching - O(N)
  • Access - O(1)

• Insertion, Removal

  • 배열의 끝에 추가 , 삭제는 O(1)이다.
  • 그러나 배열의 시작지점(중간도 마찬가지)에 추가 , 삭제는 기존의 모든 요소의 위치를 변경하게 되므로, O(N)이다.
    • 따라서 배열의 시작 부분에서 추가(unshift) 및 제거(shift) 작업은 마지막 부분에 추가 또는 제거를 하는 것으로 대체할 수 있다면 피하는 것이 좋다.
    • push, pop 메서드가 shift, unshift 메서드보다 항상 빠르다.
      (시작에 넣거나 빼면 처음부터 끝까지 영향을 받으면서 전부 인덱스를 다시 정리해야하기 때문)

• 배열 메서드의 Big O

  • O(1)

    • push , pop

  • O(N)

    • shift, unshift
    • concat
    • slice, splice
    • forEach / map / filter / reduce / etc

  • O(N*logN)

    • sort