1. 빅오 표기법
1-1. 무수한 알고리즘 해결책에 대한 평가 기준
- performance.now()를 통한 시간 차이 측정
- 컴퓨터의 연산 갯수 측정
1-2. 빅오 시간 복잡도
- 입력에 따른 연산 시간의 관계성 측정, 다소 추상적인 말이지만 '큰 흐름'에 집중
- 상수곱, 합의 연산은 단순화
1-3. 빅오 공간 복잡도
- 입력에 따라 차지하는 메모리의 관계성 측정 (공간 할당)
- Boolean, Numbers, undefiend, null은 상수 복잡도 O(1) (단순화 가능)
- String, Array, Object는 선형 복잡도 O(N)
1-4. 로그
- 지수함수의 역
- 대부분의 정렬, 탐색 알고리즘과 같이 로그 복잡도를 갖는 알고리즘들이 존재
2. 배열과 오브젝트의 성능 평가
2-1. 자바스크립트 기본 요소들의 성능
- 객체 (Object)
- 정렬이 필요 없는 경우 (배열과의 차이점)
- 빠른 접근, 입력과 제거를 원할 경우 : 상수 복잡도. O(1)
- 탐색 (특정 정보가 어떤 값에 있는지의 확인)의 경우 선형 복잡도 O(N)
- Keys(), Values(), Entries() Method 또한 선형 복잡도 O(N)
- HasOwnProperty Method : 해당 키를 갖고 있는지 참/거짓으로 반환하는 메서드로, 상수 복잡도 O(1) 가짐
- 배열 (Array)
- 정렬되어 있는 데이터
- 입력과 제거 측면에서 뒤처지는 성능
- Push / Pop : 맨 뒤에 붙히기만 하면 되므로 상수 복잡도 O(1)를 가짐
- Shitf / Unshift : 제일 앞에 새로운 요소를 배정하고 싶은 경우, 기존 요소를 한 칸씩 뒤로 미뤄야 하므로 O(N)
- 접근과 인덱싱은 상수 복잡도 O(1)
- Concat() : 배열 결합 메서드, O(N)
- Slice() : 배열 일부 참조 메서드, O(N)
- Splice() : 요소 제거 및 추가 메서드, O(N)
- Sort() : 배열 정렬 메서드, O(N * logN)
- forEach / map / filter / reduce / etc.. : O(N)
Javascript 알고리즘 / 자료구조 마스터 (유데미) 강의 수강 후 복습하며 정리한 내용입니다. 원 강의는 이곳에서 수강할 수 있습니다.
