[알고리즘]객체(Object)의 Big O

일단 객체를 언제 사용하는지 알아보자.

1. 객체는 정렬되어 있을 필요가 없다.

2. 빠른 접근과 입력, 삭제를 원할 때 좋다.

 

객체의 Big O

입력(Insertion) - O(1)
제거(Removal) - O(1)
탐색(Searching) - O(N)
접근(Access) - O(1)

 

let instructor = {  // instructor- 강사
  firstName: "Kelly",
  isInstructor: true,
  favoriteNumbers: [1, 2, 3, 4]
}

insturctor변수에 Object를 담았는데 컴퓨터가 접근할 때 단순히 firstName이라고 적혀있는 메모리 공간에 다시 접근할 수 있는 것은 아니다. 그렇기 때문에 작업을 하면서 추가적인 단계들이 있다.

주목할 점은 JavaScript가 어떤 정보를 상수 시간(O(1))안에 저장할 수 있다는 것이다.

저장하고 불러오고 수정하고 제거하는 동작은 상수 시간이기에 매우 빠르다. 

 

탐색(Searching)은 key를 찾는 것이 아닙니다. 어떠한 정보에 접근하는 시간은 상수 시간이다. 

순서가 없기 때문에 특정 값이 어디에 있는지 알 수 없다. 잠재적으로 모든 아이템에 모든 속성을 확인해야 할 수도 있다.

정확한 예는 아니지만 위 코드에서 true를 찾기위해 firstName을 확인하고 isInstructor를 확인하는 과정을 거친다.

중요한 것은 속성들이 많을 수록, n이 늘어날수록 그만큼 걸리는 시간도 늘어난다. 

 

객체 메소드의 Big O

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

 

Object.keys(instructor)를 입력하면 배열 데이터로 들어온다. O(N)

 

Object.keys(instructor)

 

Object.values도 마찬가지이다.

Object.entries(instructor)에서 entries는 작업이 조금 더 많지만 결국 O(N)으로 정리할 수 있다.

 

Object.entries(instructor)

 

instructor.hasOwnProperty("firstName") 그 값을 원하면 상수 시간으로 정보에 접근할 수 있다.

결과는 true

 

 

다음은 배열의 Big O를 알아보자.