1. 빅오 (Big O) 소개
- 효율성 체크을 위해 알고리즘 성능을 측정하고 비교한다.
- input 값의 증가에 따라 알고리즘의 실행 시간이 어떻게 변하는지에 대해 설명하는 공식적인 방법
- 입력 값의 크기와 실행시간의 관계를 나타낸다.
- 전반적인 추세에 주목한다.
2. 코드 시간 재기
- 더 나은 코드의 기준은 뭘까 ? => 속도? 가독성? 메모리 사용량?
- 보통 시간에 집중을 한다. 시간이 중요하지만 단순 시간 측정은 기기의 성능에 차이가 난다. 그렇다고해서 똑같은 기기에서는 동일하냐? 그것도 아니다. 똑같은 기기에서도 시간 측정 기록은 차이가 있다.
- 매번 새로운 방법이 나왔을 때 그것을 측정하는 것도 비용이다
- 그래서 나온것이 빅오이다.
3. 연산 갯수 세기
- 코드가 실행될 때 걸리는 정확한 시간을 초로 측정하는 것보다는 → 컴퓨터가 처리해야하는 연산의 갯수를 세면된다.
- 연산의 정확한 갯수를 세는 것보다는 전체적인 추세를 아는 것이 목적이다.
- n값이 커질수록 연산의 갯수도 늘어나는 것은 당연하다. 이렇게 n값에 따른 변화 추이를 그래프로 그렸을 때 해당 알고리즘의 추세를 알 수 있다.
▲ 시간 복잡도
4. 빅오 표현식의 단순화하기
- 항상 같은 연산 = O(1) 실행 시간에 변함이 없다. n이 커져도 같다.
- 선형 관계 (1:1) = O(n) n이 커지면 실행시간도 커진다.
실행 시간
- 산수 = O(1) (+ - / *)
- 변수 할당 = O(1)
- 인덱스를 이용해 배열 엘리먼트에 접근 = O(1)
- 키를 통해 오브젝트 엘리먼트에 접근 = O(1)
- 루프 ⇒ 루프 길이에 따라
// 무조건 반목문이 들어간다고 해서 최소 O(n)은 아니다.
// 로직을 어떻게 짜느냐에 따라 다르다.
// 예외
function logAtMost5(n) {
for (let i = 1; i <= Math.min(5, n); i++) {
console.log(i);
}
}
logAtMost5(1); // 1
logAtMost5(3); // 1 2 3
logAtMost5(5); // 1 2 3 4 5
logAtMost5(10); // 1 2 3 4 5
logAtMost5(100000); // 1 2 3 4 5
// 추세를 보면 n값이 커져도 항상 5를 넘지 않는다
// 5미만의 n 값들은 n값의 커짐에 따라 별로 영향을 주지 않는다
// 그렇기에 빅오는 O(1)이다.
5. 공간 복잡도
- 시간 복잡도 → 입력값(n)에 따른 알고리즘의 실행 속도이다
- 입력값(n)이 커질수록 알고리즘이 얼마나 많은 공간을 차지하는지 고려한다. (메모리 사용량)
- 입력되는 것을 제외하고 알고리즘 자체가 필요로 하는 공간이다.
- 공간은 입력의 크기에 따른 리턴값 간의 관계
- 원시값들 (boolean, numbers, undefined, null) 은상수 공간(constant space), O(1), 항상 똑같은 공간을 차지 = 불변 공간이라는 뜻
- String, Reference type, array, object = O(n) space
- string → 문자의 길이
- array → 배열의 길이
- object → 키의 개수
6. 객체(Object)의 빅오(Big O)
객체는 정렬되어 있지 않다.
저장, 접근, 제거, 수정의 경우 O(1)이 걸린다.
탐색은 단순하게 key에 접근하는 것이 아닌 value를 가져와야하기에 O(n)이 걸린다.
const obj = { name: "jack", age: 0 };
// 'jack' 이라는 값이 어디에 저장되어 있는가를 알기위해서는 모든 `key`값을 돌며 `value`를 체크해야한다.
Object.keys, Object.values, Object.entries 메소드들의 경우 O(n)이 걸린다. 객체를 돌며 다 배열에 담아 반환해야하기 때문이다.
hasOwnProperty의 경우 O(1)이 걸린다. key가 있는지 없는지 바로 접근이 가능하기 때문이다.
7. 배열(Array)의 빅오(Big O)
배열은 정렬된 데이터이다. 그렇기에 각 값에 인덱스가 붙어있다.
접근의 경우 O(1)이 걸린다. index로 바로 접근하면 되기 때문이다.
탐색은 객체와 동일하게 O(n)이 걸린다.
저장의 경우 어디에 저장하느냐에 따라 빅오가 달라진다. push메소드는 배열의 끝에 저장하기 때문에 O(1)이 걸린다. unshift메소드는 배열의 처음에 저장하기 때문에 O(n)이 걸린다.
제거의 경우도 어디를 제거하느냐에 따라 빅오가 달라진다. pop 메소드는 배열의 끝 값을 제거하기 때문에 O(1)이 걸린다. shift메소드는 배열의 처음 값을 제거하기 때문에 O(n)이 걸린다.
왜? 같은 저장, 제거인데 다르죠?
- 인덱스 번호의 재배치 때문이다.
- 배열의 끝에 저장/제거하는 경우는 끝에 값이 있기 때문에 다른 값들의 인덱스는 변화가 없다.
- 하지만 배열의 처음에 저장/제거하는 경우는 그 작업을 수행한 후 나머지 값들의 인덱스를 재배치 해주어야하기 때문이다.
// 기존의 0번 인덱스에 위치한 값은 "A"이지만 shift 호출이후 "B"로 바뀌게 된다.
// 즉, 0번 인덱스의 값이 제거가 되면 나머지 값들의 인덱스 번호가 하나씩 떙겨져 재배치 된다.
const arr = ["A", "B", "C", "D"];
arr[0]; // "A"
arr.shift();
arr[0]; // "B"
- 비어있는 배열의 경우를 제외하고 push, pop메소드는 shift, unshift보다 빠르다.
- push, pop메소드의 경우O(1)이 걸린다.
- shift, unshift, concat, slice, splice메소드의 경우 O(n)이 걸린다.
- sort메소드의 경우 O(n* log n)이 걸린다. (추후 포스팅)
- forEach, map, filter, reduce메소드의 경우 O(n)이 걸린다.
피드백은 언제나 환영입니다.