본 포스팅은 Colt Steele의 JavaScript 알고리즘 & 자료구조 마스터클래스를 수강하며 정리한 노트입니다.
https://www.udemy.com/course/best-javascript-data-structures/
15. 객체의 빅오
- 객체는 정렬되어있을 필요가 없을 때 잘 작동한다.
- 빠른 접근, 입력과 제거를 원할 때 좋다.
정렬만 뺀 나머지 부분들에서는 성능이 매우 좋다.
객체에는 시작과 종료라는 개념이 존재하지 않다.
Insertion - O(1)
Removal - O(1)
Searching - O(N) => 희귀. 값을 찾아 순환
Access - O(1)
- 객체메서드 시간복잡도
Object.keys - O(n)
Object.values - O(n)
Object.entries - O(n)
hasOwnProperty - O(1) => 키를 전달하면 유무여부만 가르쳐주므로 상수시간.
16. 배열 안의 데이터에 접근이 느린 이유
- 정렬이 필요할 때 배열을 이용
- 접근과 삭제시 성능이 많이 떨어짐.
Insertion - depentds... 맨 뒤에 추가할 경우 O(1), 그러나 중간에 추가할 경우 인덱스가 한개씩 밀리는 일이 발생. 즉 O(n).
Removal - depentds... 중간 값을 삭제할 시 인덱스가 한개씩 밀리기 때문에 O(n).
Searching - O(N) => 배열의 크기가 클 수록 탐색에 걸리는 시간도 증가.
Access - O(1) => 인덱스는 값에 접근시의 지름길.
accessing is fast no matter what
- 배열메서드 시간복잡도
push - O(1) 배열의 끝에 추가
pop - 0 (1) 배열의 끝에 삭제
shift - O(n) 배열의 앞에 추가, 모든 인덱스 다시 정리..
unschift - O(n) 배열의 앞에 삭제, 모든 인덱스 다시 정리..
concat - O(n) 결합할 배열의 크기에 비례
slice - O(n) 복제할 배열의 크기에 비례
splice - O(n) 복제할 배열의 크기에 비례
sort O(n log n) 배열정리는 O(n)보다 더 복잡.
forEach/map/filter/reduce/etc. - O(n) 순환하며 작업을 수행.
