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

Object

• 특징 : Unordered, key value pairs
• 객체를 언제 사용하는가?
  • 순서가 필요 없을 때
  • 빠른 접근(삽입, 제거)이 필요할 때
• 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(1)

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