빅오 표기법
좋은 코드를 판단할 때는 여러가지 기준이 있을 수 있지만 빅오 표기법은 객관적이며 변하지 않는 기준으로 코드의 효율성을 비교하기위한 표기법이다.
시간 복잡도과 공간 복잡도를 나타나는데 주로 사용된다.
시간 복잡도
알고리즘이 얼마나 빠르게 실행하지를 나타낸다.
이름은 시간 복잡도이지만 실제 코드가 실행되는 시간을 기준으로 하지 않고 연산 갯수를 기준으로 판단한다.
왜냐라면 시간은 가변적이기 때문이다. 시간은 컴퓨터의 사양에 따라서 변할수도 있고 심지어 같은 컴퓨터에서도 실행할 때마다 시간이 조금씩 바뀐다. 반면 연산 갯수는 어떤 컴퓨터에서든 동일하기 때문에 연산 갯수를 기준으로 판단한다.
연산 갯수
연산 갯수는 정확한 연산 갯수를 의미하진 않고 단순화한 갯수를 의미한다. 예를 들어 아래의 함수의 연산 갯수는 대략 5n +2 번이다. 빅오표기법으로 표기하면 O(f(n))으로 표기할 수 있다.
function addUpTo(n) {
let total = 0; // 1번
for (let i = 1; i <= n; i++) { // i = 1 1번, i <n 판단에 n번, i++ 계산에 n번, i재할당 n번
total += i; // 재할당에 n번, i 더하기에 n번
}
return total;
}즉, 정확한 연산 갯수보다는 연산 갯수가 증가하는 추세를 보는 것이다.
변수가 증가 함에 따라 연산 갯수가 y = x 추세로 증가한다면 O(n),
연산 갯수가 상수 그래프 추세로 증가한다면 O(1),
연산 갯수가 2차함수 그래프 추세로 증가한다면 O(n^2)이다.
예를 들어 O(2n) 대신 O(n)으로 O(500)대신 O(1)로 O(13n^2) 대신 O(n^2)로 단순화해 표기한다.
공간 복잡도
입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지하는 지를 나타낸다.
시간 복잡도와 표기하는 방법은 같지만 입력이 커짐에 따라 알고리즘이 차지하는 공간 변화의 경향을 나타낸다.
기본적인 규칙
- 원시형 자료 (booleans, numbers, undefined, null)은 모두 불변적인 공간을 가진다.
다시 말해 1이나 1000이나 차지하는 공간은 같다. - 그러나 문자형은 O(n)의 공간 필요하다. 문자열의 길이에 따라 차지하는 공간도 늘어난다.
- 참조형 자료 또한 대부분이 O(n)의 공간을 차지한다.
아래의 함수는 시간 복잡도는 O(n)이 였지만 공간 복잡도는 O(1)이다. 숫자 값 할당밖에 없는데 숫자는 불변적인 공간을 가지기 때문이다.
하지만 만약에 i를 빈배열에 담는 함수였다면 공간 복잡도는 O(n)이 였을 것이다.
function sum(arr) {
let total = 0;
for (let i = 0; i < arr.length; i++) {
total += arr[i];
}
return total;
}
객체의 성능 평가
- 입력- O(1)
- 삭제- O(1)
- 탐색- O(N)
- 접근- O(1)
객체는 순서가 없으므로 삭제, 삽입, 접근 모두 O(1)의 성능을 가진다.
다만 탐색의 경우 모든 객체를 둘러봐야하므로 O(n)의 성능을 가진다.
객체 메서드의 빅오
- Object.keys - O(N)
- Object.values - O(N)
- Object.entries - O(N)
- hasOwnProperty - O(1)
배열의 성능 평가
- 입력- 배열 맨 앞에 삽일할 경우 O(N), 맨 뒤에 삽일할 경우 O(1)
- 삭제- 배열 맨 앞에 삭제할 경우 O(N), 맨 뒤에 삭제할 경우 O(1)
- 탐색- O(N)
- 접근- O(1)
배열은 순서가 있다. 그래서 배열의 맨 앞에 요소를 삽입하거나 삭제할 경우 인덱스가 모두 하나씩 밀리기때문에 O(N)의 성능을 가진다. 반면 뒤에 삽입이나 삭제할 경우 기존의 인덱스의 변화가 없기때문에 O(1) 성능을 가진다.
즉, push와 pop이 unshift와 shift보다 좋은 성능을 가진다.
배열을 접근할 때는 모든 요소를 둘러보는 것이 아니라 인덱스를 통해 바로 접근할 수 있으므로 O(1)의 성능을 가진다.
탐색은 객체와 마찬가지로 모두 둘러봐야하므 O(n)의 성능을 가진다.
배 메서드의 빅오
- push - O(1)
- pop - O(1)
- shift - O(N)
- unshift - O(N)
- concat - O(N)
- slice - O(N)
- splice - O(N)
- sort - O(N * log N)
- forEach/map/filter/reduce/etc. - O(N)
참고) [Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스