자바스크립트로 알고리즘을 공부하는 자료는 너무 귀한 듯 싶어, 정리해보고자 합니다.
Big O 표기법
Big O 표기법은 O(n) 과 같이 표기합니다.
Big O의 의미는 이러합니다.
Why is it called the Big O?
Big O notation is named after the term "order of the function", which refers to the growth of functions
빅오 표기법은 "함수의 순서"를 따서 명명되었습니다.
Big O 표기법은 이렇게 사용됩니다.
- 성능, 코드의 효율성 표시
- 입력된 내용이 늘어날 수록 알고리즘에 실행 시간/메모리를 차지하는 공간이 어떻게 변하는지 설명하는 방식.
- 동작의 입력값이 늘어나는 것과, 실행시간이 변하는 관계를 나타냄
즉, 입력과 실행시간의 관계 혹은 입력과 연산이 차지하는 공간의 관계입니다.
빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용됩니다.
표현
O(1)
- 입력값의 변화와 상관없이 항상 연산 개수가 동일
O(n)
- 입력값의 크기에 따라 연산 개수가 달라짐.
O(n^2)
- O(n) 연산 속 O(n)이 있으면 n*n. 따라서 O(n^2)
O(log n)
- 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n log n)
- 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가짐
O(C^n)
- 문제를 해결하기 위한 단계의 수가 주어진 상수값 C 의 n 제곱.
시간 복잡도
Big O 표기법은 시간복잡도를 나타낼 수 있습니다.
시간 복잡도란 말 그대로 연산 처리 속도가 input의 변화에 따라 어떤 양상을 띄는지를 표현합니다.
예시를 살펴보겠습니다.
시간 복잡도 예시
입력값 n (n는 0보다 큰 자연수)이 있고 1부터 .n까지의 자연수를 모두 더한 값을 보여주는 함수를 작성해봅시다.
우선 아래와 같이 작성할 수 있습니다. for 구문을 사용하는 기초적인 방법입니다.
function sumTo(n) {
let result = 0;
for(let i=0; i<=n; i++) {
result += i;
}
return result;
}여기에 사용된 시간복잡도는 Big O 표기법으로 나타내면 O(n) 입니다.
시간 복잡도를 따져볼 때에는 연산이 몇 번 이뤄지는지를 살펴보는 것이 중요합니다.
코드를 다시 보면, n의 길이에 따라서 for loop를 도는 횟수가 늘어납니다.
function sumTo(n) {
let result = 0;
for(let i=0; i<=n; i++) { // 연산
result += i; // 연산 (덧셈과 할당)
}
return result;
}만약 n이 10이라면 loop가 10번 반복되며, 부수적인 연산들도 10번 반복됩니다.
그럼 n이 100이 되고, 1000이 된다면? loop가 도는 시간은 한없이 늘어나겠죠.
아래처럼 테스트를 해보죠.
function sumTo(n) {
let result = 0;
for(let i=0; i<=n; i++) {
result += i;
}
console.log(result)
return result;
}
console.time('sumToTime')
sumTo(1000) // input값 변경하며 테스트
console.timeEnd('sumToTime')sumTo(10) 을 수행하는 데에는 sumToTime: 0.091064453125 ms 가 콘솔에 찍혔습니다.
반면 sumTo(100000) 을 수행하는 데에는 sumToTime: 2.08203125 ms 보다 긴 시간이 소요됐죠.
이 함수의 시간 복잡도를 낮추기 위해서는 연산의 수가 줄어들어야 합니다.
n까지의 수를 모두 더하는 수학 공식인 n(n+1) / 2 을 사용할 수 있습니다.
function sumTo(n) {
let result = (n * (n+1))/2
}
console.time('sumToTime')
sumTo(1000)
console.timeEnd('sumToTime')이렇게 공식을 바꾸면, sumTo(100000) 을 똑같이 입력해도 sumToTime: 0.02294921875 ms 밖에 나오지 않습니다.
물론 수가 더 커지든, 작아지든 상관없습니다.
input값의 변화가 연산 속도에 지장을 주지 않기 때문에 고친 함수의 시간 복잡도는 O(1) 입니다.
또 다른 경우를 보겠습니다.
function logLoopMax10(n) {
for (let i = 0; i <= Math.min(n, 10); i++) {
console.log(i);
}
}위 코드는 O(n)일까요? O(1)일까요?
언뜻 O(n)처럼 볼 수도 있겠지만, 아무리 n이 커져도 n과 10을 비교해 더 적은 수만큼 loop를 돌기 때문에, 위 함수의 시간 복잡도는 O(1)입니다.
공간 복잡도
공간 복잡도는 메모리를 얼마나 차지하는지에 따른 복잡도입니다.
시간 복잡도와 헷갈리지 않게 주의하세요.
공간 복잡도는 연산의 개수에 따라 달라지지 않고, input 값에 따라 할당되는 메모리가 어느정도인지를 나타냅니다.
먼저 자바스크립트의 자료형에 따라 달라지는 공간을 보겠습니다.
- 불변 공간
- Boolean
- Number (크기와 상관없이 같은 공간 차지)
- undefined
- null
- O(n)
- String (문자열 길이에 따라 달라짐)
- reference
- Array (배열의 길이에 따라 달라짐)
- Object (key-value 쌍의 개수에 따라 달라짐)
int, double, float 등으로 차지하는 메모리 공간에 따라 type이 달라지는 다른 언어(Java 등)와 달리 자바스크립트의 숫자는 Number 타입 하나로, 차지하는 크기가 모두 동일합니다.
예제를 보죠.
function test(n) {
for (let i = 1; i <= n; i++) {
console.log(i)
}
}위 코드의 공간 복잡도는 어떻게 나타낼까요?
시간 복잡도에서는 n에 따라 연산 횟수가 늘어나니 O(n)이었을테지만, 공간 복잡도에서는 O(1)입니다.
입력값의 크기와 상관없이 상수 시간 O(1)을 가진다는 것이죠.
그 이유는 다음과 같습니다.
function test(n) {
for (let i = 0; i <= n; i++) { // let i 로 메모리 할당
console.log(i)
}
}실제로 할당된 변수는 i밖에 없기 때문이죠.
또 다른 예제를 보겠습니다.
배열을 파라미터로 넘겨받고 각각의 요소에 2배를 하여 새 배열로 돌려주는 함수입니다.
function double(arr) {
let tempArr = [];
for (let i = 0; i < arr.length; i++) {
tempArr.push(2 * arr[i]);
}
}만약 입력받은 arr가 10개의 요소를 가지고 있다면 돌려받는 배열 또한 길이가 10일 것이고,
100만개를 가지고 있다면 output 또한 길이가 100만인 배열일 것입니다.
그러면 이 함수의 공간복잡도는 무엇일까요? 바로 O(n)입니다.
배열의 길이에 따라 공간을 차지하기 때문이죠.
간단하게 자바스크립트의 시간/공간 복잡도를 알아봤습니다.
댓글