[알고리즘] Big O Of Arrays and Objects
1. 배열과 오브젝트 성능 평가
Javascript에서 objects의 keys-values쌍은 index가 따로 없기 때문에 삽입, 제거, 탐색, 접근 등의 작업에 드는 시간이 arrays와 다르다.
- objects의 keys-values는 index(순서)가 없기 때문에 상수시간 O(1)이 걸린다
- 하지만 value를 찾을때는 모든 keys를 확인해야해서 선형 시간 O(n)이 걸린다
1) 객체(Objects)
- 객체는 순서가 없지만 key와 value을 사용해 빠르다는 장점이 있다.
- Big O로 보는 성능은 다음과 같다.
- 삽입(Insertion) ⇒ O(1)
- 삭제(Removal) ⇒ O(1)
- 검색(Searching) ⇒ O(N)
- 접근(Access) ⇒ O(1)
2) 객체 순회
Object.keys()
- 객체의 키 목록을 배열로 리턴한다.
- 객체 내장 메서드가 아니고, 객체 생성자인 Object 가 직접 가지고 있는 메서드.
let instructor = {
firstName:"Abel",
isInstructor:true,
favoriteNumbers: [1,2,3,4]
}
console.log(Object.keys(instructor));
[Running] node "/workspaces/codespaces-blank/ObjectBigO.js"
[ 'firstName', 'isInstructor', 'favoriteNumbers' ]
[Done] exited with code=0 in 0.03 seconds
Object.entries()
- value 값을 배열로 반환하는 Object.values() 와 객체의 key, value 값을 배열로 반환
//시간복잡도가 훨씬 낮음
let instructor = {
firstName:"Abel",
isInstructor:true,
favoriteNumbers: [1,2,3,4]
}
console.log(Object.entries(instructor));
[Running] node "/workspaces/codespaces-blank/ObjectBigO.js"
[
[ 'firstName', 'Abel' ],
[ 'isInstructor', true ],
[ 'favoriteNumbers', [ 1, 2, 3, 4 ] ]
]
[Done] exited with code=0 in 0.038 seconds
3) 배열(Array)
- 순서가 정해져 있어 객체보다 시간이 좀 더 오래 걸림.
- 정렬될 필요가 있는 데이터, 정렬되어 있는 데이터를 보관하는데 유리함
배열 시작에서 작업을 하는것이 끝에서 하는것보다 더 느리다
- 삽입 ⇒ 배열 시작 : O(N), 배열 끝: O(1)
- 삭제 ⇒ 배열 시작 : O(N), 배열 끝: O(1)
- 검색 ⇒ O(N)
- 탐색 ⇒ O(N)
Big O Notation
| push | O(1) |
|---|---|
| pop | O(1) |
| shift | O(n) |
| unshift | O(N) |
| concat | O(N) |
| slice | O(N) |
| splice | O(N) |
| sort | O(N * ㏒N) |
| 고차함수(forEach/map/filter/reduce) | O(N) |
- pop, push은 인덱스를 사용해서 접근하는 것과 똑같고 상수 시간걸림 빠름
- 배열의 기본적인 연산, 메소드들은 보통 O(N).
2. 정리
- 객체는 거의 모든것을 더 빠르게 하지만 , 정렬되어 있지 않다
- 배열은 정렬 되어 있지만 ,끝에 추가하고 제거하는 작업이 느림 , 시작에 넣거나 빼면 처음부터 끝까지 영향 받고 Index를 다시 정리해야함
