[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 3

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

Object를 사용할 때

• 정렬할 필요가 없을 때
• 빠르게 접근, 입력, 제거를 원할 때

Object의 시간복잡도

• Insertion: O(1)
• Removal: O(1)
• Searching: O(N)
• Access: O(1)

Method의 시간복잡도

• Object.kyes: O(N)
• Object.values: O(N)
• Object.entries: O(N)
• hasOwnProperty: O(1)

Arrays를 사용할 때

• 순서가 필요할 때
• 빠르게 접근, 입력, 제거를 원할 때

Arrays의 시간복잡도

• Insertion: 상황에 따라 다르다
• Removal: 상황에 따라 다르다
• Searching: O(N)
• Access: O(1)

Arrays 작동들의 시간복잡도(굳이 알 필요 없)

• push, pop: O(1)
• shift,unshift, concat, slice, splice: O(N)
•  sort: O(N * log N)
•  forEach, map, filter, reduce, etc.: O(N)

배열의 끝에 추가 혹은 끝의 것을 제거하는 push, pop은 인덱스를 바꾸지 않으므로 걸리는 시간이 항상 같다. 다만 인덱스를 바꿔야 하는 작업인 shift, unshift는 선형 시간이 걸린다. concat은 여러 배열을 합치는 것이므로 늘어난 배열 원소의 갯수만큼 걸린다. slice는 배열의 일부를 가져오므로, 최대로 가져오는 전체일 경우 선형시간이 걸린다. splice은 배열 중간에 삽입하는 것이 가능하므로, 최대로 걸리는 시간은 선형시간이다.