[자료구조와 알고리즘] 유데미 강의 "JavaScript 알고리즘 & 자료구조 마스터클래스" 정리(섹션 3: 배열과 오브젝트의 성능 평가)

섹션 3: 배열과 오브젝트의 성능 평가

📌 객체의 빅오

1. 객체 키, 값의 삽입, 삭제, 접근의 경우

• Insertion, Removal, Access → O(1) 

 

2. 객체의 키로 접근하지 않고 값으로 탐색하는 경우

• Searching → O(n)

 

3. 객체 메서드의 빅오

O(n)

• Object.keys
• Object.values
• Object.entries

O(1)

• Object.hasOwnProperty

let instructor = {
  firstName: "김일남",
  isInstructor: true,
  favoriteNumbers: [1,2,3,4]
}
instructor.hasOwnProperty("firstName"); // true

 

📌 배열의 빅오

1. 배열 앞이나 중간 인덱스에 요소 삽입, 삭제

배열의 끝에서 추가, 삭제가 일어난다면 O(1)이지만 그렇지 않다면 추가되는 인덱스 위치에 따라 성능이 결정된다. 추가, 삭제된 요소 뒤에 있는 인덱스가 모두 변경되기 때문이다.

• Insertion, Remova → O(n)

 

2. 배열 요소 탐색

• Searching → O(n)

 

3. 배열 인덱스로 접근

• Access →  O(1)

 

4. 배열 메서드의 빅오

O(1)

• push, pop

O(n)

• shift, unshift, concat, slice, splice, forEach, map, filter, reduce 등

O(n * logn)

• sort