시간을 가지고 천천히 진행하자
빅오 표기법은 왜 필요할까?
"이 알고리즘의 빅오 표기법을 설명해주세요" 만약 이런 질문이 내게 온다면 난 아마 그 자리에서 얼어버릴 지도 모른다. 빅오 표기법은 대학생 때 배우고 내 머릿속 지우개로 지운 지 오래이기 때문이다.
하지만 개발을 하다 보면 결국 성능이라는 문제를 다시 마주치게 된다. 입력값이 커질수록 이 코드가 얼마나 느려질 수 있는지를 설명하기 위한 공통 언어가 바로 빅오 표기법이다.
빅오는 인풋의 크기(n) 와 실행 시간(또는 메모리 사용량) 사이의 관계를 표현하는 방법이다. 정확한 실행 시간을 재는 것이 아니라, n이 커질 때 증가하는 추세를 보는 개념이다.
O(1) : 입력 크기와 무관한 시간
예를 들어 아래와 같은 함수가 있다고 치자.
function addUpTo(n) {
return n * (n + 1) / 2;
}이 함수에서 n이 커질수록 실행 시간은 어떻게 변화할까? 1부터 10, 100, 10000000까지 어떤 값을 넣어도 연산 횟수는 항상 같다.
그래서 이 함수의 시간복잡도는 O(1) 이다. 입력값의 크기와 상관없이 항상 일정한 시간이 걸린다는 의미다.
O(n) : 입력 크기에 비례하는 시간
이번에는 for문이 들어간 함수를 살펴보자.
for (let i = 0; i < n; i++) {
console.log(i);
}연산의 개수는 n에 비례한다. 앞에 1이 곱해지든, 1000이 곱해지든 결국 중요한 것은 n번 반복된다는 사실이다.
그래서 이런 경우 시간복잡도는 O(n) 이다.
n이 2배가 되면 실행 시간도 2배가 된다.
O(n²) : 중첩 루프
for문이 두 번 이상 중첩된다면 어떻게 될까?
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(i, j);
}
}루프가 중첩되어 있기 때문에 연산 횟수는 n × n, 즉 n²이 된다. 그래서 시간복잡도는 O(n²) 이다.
이건 상당히 그래프 폭이 클 것이다. 4만 되어도 16, 100만 되어도 10000으로 불어나기 때문이다.
n이 커질수록 실행 시간은 기하급수적으로 증가한다.
빅오 표현법 단순화하기
빅오 표기법에는 몇 가지 중요한 규칙이 있다.
1. 상수는 무시한다
산수 연산은 모두 상수 시간이다. 2 + 2를 처리하는 것이나 1000 + 2를 처리하는 것이나 차이는 없다.
O(n + 10) → O(n)
O(100 * n) → O(n)2. 가장 큰 차수만 남긴다
O(n + n + n + n) → O(n)
O(n² + n³) → O(n³)n이 충분히 커지면 가장 큰 차수의 항이 성능을 지배하게 된다.
조건문이 포함된 루프의 시간복잡도
for (let i = 0; i <= Math.max(5, n); i++) {}n이 5보다 클 수도 있으므로 최악의 경우 n번 반복된다. 따라서 시간복잡도는 O(n) 이다.
for (let i = 0; i <= Math.min(5, n); i++) {}n이 아무리 커도 최대 5번만 반복된다. 그래서 시간복잡도는 O(1) 이다.
빅오는 항상 최악의 경우(worst case) 를 기준으로 판단한다.
공간 복잡도는 무엇일까?
시간복잡도만큼 중요한 개념이 공간복잡도다. 입력 크기에 따라 얼마나 많은 추가 메모리를 사용하는지를 나타낸다.
function onlyElementsAtEvenIndex(array) {
var newArray = Array(Math.ceil(array.length / 2));
for (var i = 0; i < array.length; i++) {
if (i % 2 === 0) {
newArray[i / 2] = array[i];
}
}
return newArray;
}이 함수는 입력 배열의 크기에 비례하는 새로운 배열을 만든다. 그래서 공간복잡도는 O(n) 이다.
function subtotals(array) {
var subtotalArray = Array(array.length);
for (var i = 0; i < array.length; i++) {
var subtotal = 0;
for (var j = 0; j <= i; j++) {
subtotal += array[j];
}
subtotalArray[i] = subtotal;
}
return subtotalArray;
}이 함수는 중첩 루프를 가지고 있어 시간복잡도는 O(n²)이지만, 추가로 사용하는 메모리는 결과 배열 하나뿐이다.
그래서 공간복잡도는 O(n) 이다.
시간복잡도와 공간복잡도는 서로 다를 수 있다.
객체와 배열의 시간복잡도
객체(Object)
객체는 정렬되어 있지 않고, 키 기반으로 접근한다. 그래서 다음 연산들은 대부분 빠르다.
삽입: O(1)
삭제: O(1)
접근: O(1)
순서가 중요하지 않은 데이터라면 객체가 유리하다.
배열(Array)
배열은 정렬된 자료구조다.
인덱스를 통한 접근: O(1)
맨 뒤에 추가(push): O(1)
맨 뒤 제거(pop): O(1)
하지만 앞쪽에서 삽입하거나 제거하면 문제가 생긴다.
앞에 추가(unshift): O(n)
앞 제거(shift): O(n)
앞쪽 요소가 변경되면 뒤에 있는 모든 인덱스를 다시 정리해야 하기 때문이다. 그래서 push와 pop이 shift와 unshift보다 빠르다.
배열 메소드의 빅오
push / pop : O(1)
shift / unshift : O(n)
concat : O(n)
slice : O(n)
splice : O(n)
sort : O(n log n)
forEach / map / filter / reduce : O(n)
메소드 하나하나의 시간복잡도를 알고 있으면 코드를 작성할 때 성능을 고려하며 더 좋은 코드를 만들 수 있다.
