정식으로 입력된 내용이 늘어날수록 알고리즘에 실행 시간이 어떻게 변하는지 설명하는 공식적인 방식이다.
코드 분류, 숫자로 코드의 성능을 빅오 형식으로 표기할 수 있다.
좋은 코드의 기준은 뭘까? 브라우저에서 실행되는 속도, 코드의 간결성 등 기준은 많다.
그 기준을 측정하기 위하여 브라우저의 내장 객체인 performance
를 이용해 동일한 기능을 담은 두 개의 함수에서 함수 실행 시간을 측정해 보았다.
addUpTo 함수 실행 전과 후에 performance.now()를 실행하여 그 시간만큼 빼주었다.
function addUpTo(n) {
let total = 0;
for (let i = 1; i <= n; i++) {
total += i;
}
return total;
}
var t1 = performance.now();
addUpTo(1000000000);
var t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`)
실행 결과
function addUpTo(n) {
return n * (n + 1) / 2;
}
var time1 = performance.now();
addUpTo(1000000000);
var time2 = performance.now();
console.log(`Time Elapsed: ${(time2 - time1) / 1000} seconds.`)
실행 결과
결과만 보면 뒤의 함수가 더 좋은 코드라고 할 수 있다.
하지만 책정된 시간이 매번 다르고, 기기사양에 따라서도 결과는 달라질 수 있기 때문에 좋은 코드라고 말할 수 있는 정확성이 떨어진다. 게다가 빠른 알고리즘에서는 정말 짧은 시간안에 처리되기 때문에 속도 측정 정확도가 떨어질 수 있다.
그래서 빅오 표기법에서는 시간 복잡도와 공간 복잡도를 기준으로 좋은 코드를 판단한다.
시간 복잡도는 함수를 컴퓨터가 실행해야 하는 연산의 갯수의 관점에서 본다.
연산의 갯수와 n의 값에 따른 연산 횟수를 따져보며 연산에 걸리는 시간을 유추한다.
function addUpTo(n) {//3번의 연산(덧셈 1, 곱하기 1, 나누기 1)
return n * (n + 1) / 2;
}
function addUpTo(n) {//셀 수 없는 연산..(딱봐도 세기 귀찮은 연산 횟수)
let total = 0;//= 도 연산(비교, comparisons)
for (let i = 1; i <= n; i++) {
total += i;
}
return total;
}
빅오(O = f(n))는 어떤 함수에 입력한 값이 늘어나는 것과 함수 실행 시간이 변하는 관계를 의미한다.
공간 복잡도는 n이 커질수록 입력이 커진다는 것을 가정하며 함수를 사용되는 메모리의 양,즉 알고리즘 자체가 필요로 하는 공간의 관점에서 본다.
function sum(arr) {//O(1)의 공간 차지
let total = 0;
for (let i = 0; i <= arr.length; i++) {
total += arr[i];
}
return total;
}
아래의 함수에서 차지하는 공간은 arr(입력된 배열)의 크기에 비례해서 커진다.
function double(arr) {//O(n)의 공간 차지
let newArr = [];
for (let i = 0; i <= arr.length; i++) {
newArr.push(2 * arr[i]);
}
return newArr;
}
로그, 로그함수는 지수함수의 역함이다.
시간 복잡도와 공간복잡도 외에 로그로 알고리즘을 평가할 수 있다.
곱셈을 덧셈으로 변환시켜 매우 큰 수 또는 작은 수를 계산하는데 편리함을 주는 수 표현 방식이다.
데이터가 2배로 증가할 때, 연산수가 1 단계 씩 늘어나는 형태를 말한다.
데이터가 많아질수록 성능이 우수하다.
그 숫자가 1보다 작아지기 전에 2로 나눠지는 횟수다.
O(log n)
출처: JavaScript 알고리즘 & 자료구조 마스터클래스 - 빅오 표기법
깃정리: https://github.com/jcrs0907/js_algorithm_structures