배열과 오브젝트의 성능 평가

yejichoi·2023년 3월 29일

Algorithm

목록 보기

2/4

🧺 Object

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

Big O of Object

삽입(Insertion) ⇒ O(1)
삭제(Removal) ⇒ O(1)
검색(Searching) ⇒ O(N)
접근(Access) ⇒ O(1)

Big O of Object Methods

Object.keys - O(N)

객체의 키 목록을 배열로 리턴

const obj = {
  name: 'melon',
  weight: 4350,
  price: 16500,
  isFresh: true
}

Object.keys(obj) // ['name', 'weight', 'price', 'isFresh']

Object.values - O(N)

Object.entries - O(N)

hasOwnProperty - O(1)

Boolean 값으로 반환

let obj = {
  name: "kim",
  age: 30,
  height: 172,
};
 
console.log(Object.keys(obj)); //[ 'name', 'age', 'height' ]
console.log(Object.values(obj)); //[ 'kim', 30, 172 ]
console.log(Object.entries(obj)); //[ [ 'name', 'kim' ], [ 'age', 30 ], 
//[ 'height', 172 ] ]
console.log(obj.hasOwnProperty("height")); //true

🔐 Array

Big O of Array

삽입 - 맨 앞일 때: O(N), 맨 뒤일 때: O(1)
삭제 - 맨 앞일 때: O(N), 맨 뒤일 때: O(1)
접근 - O(1)
탐색 - O(N)

Big O of Array Methods

push - O(1)
pop - O(1)
shift - O(N)
unshift -O(N) =>push와 pop이 shift와 unshift 작업보다 빠름(비어 있는 배열일때 제외)
concat - O(N + M) = O(N) : 여러 배열을 합쳐주는데 결합할 배열이 커질수록 끝에 붙일 배열의 크기만큼 시간도 그만큼 늘어날것
slice - O(N) : 배열의 전체 혹은 일부를 복사함, 얼마나 복사할지에 따라 다름 = 배열의 길이에 따라 다름
splice -O(N) : 인수가 2개일 때에는 삭제, 3개 이상일 때에는 추가
sort - O(N * logN)
고차함수(forEach/map/filter/reduce/etc. - O(N)

📍 배열의 기본적인 연산, 메소드들은 보통 O(N)
접근, pop, push은 인덱스를 사용해서 접근하는 것과 똑같고 상수 시간걸림 빠름