1. 알고리즘 평가의 필요성
한 가지 문제를 푸는 방법은 여러가지가 있을 수 있다. 예를 들어, 1 부터 N 까지 수들의 합을 구하는 알고리즘을 작성한다고 하자.
const argo1 = num => {
let sum = 0;
for (let i = 0; i < num; i++) {
sum += i;
}
return sum;
};
const argo2 = num => {
return (n * (n + 1)) / 2;
};
위의 두 가지 알고리즘 중 어느 것이 더 나은 알고리즘일까?
이런 상황에서 더 나은 알고리즘을 결정해야 하는 필요성이 생겼고, 이에 따라 등장한것이 시간, 공간 복잡도와 Big-O 표기법이다.
2. 시간, 공간 복잡도
알고리즘의 성능을 평가하는 데 가장 중요한 것이 시간/공간 복잡도이다. 컴퓨터가 사용하는 리소스 중 시간과 메모리를 말한다고 이해하면 된다.
복잡도를 이야기할때 중요한 부분은 입력값이 변해도 변하지 않는 부분 (정적 복잡도)을 제외한, 입력값에 따라 변하는 부분 (동적 복잡도)이다. 아래 코드를 보면 쉽게 이해할 수 있다.
// 1부터 입력받은 수까지 출력하는 간단한 함수이다.
const countUntil = num => {
console.log('start');
for (let i = 1; i <= num; i++) {
console.log(i);
}
console.log('end');
};
위 함수의 시간 복잡도에서 영향을 미치는 부분은 반복문이 num 만큼 도는 부분이다. 그 앞 뒤로 콘솔에 출력하는 부분들은 입력값과 상관없이 정해진 횟수만큼만 실행되기 때문에 큰 영향을 미치지 않는다.
또한 공간 복잡도는 개인용 컴퓨터의 램이 4 기가, 8 기가를 넘어서 16, 32 기가까지 보편화된 현재에는 시간 복잡도에 비해 중요성이 많이 줄었다.
유의미한 공간 복잡도의 예시는 재귀알고리즘을 실행할 때 쌓이는 콜 스택의 크기 정도가 있겠다.
3. BIG-O 표기법
이런 복잡도 개념을 좀 더 체계화/표준화/단위화 시킨 것이 BIG-O (그리고 세타와 오메가 표기법이 있지만 압도적으로 많이 쓰이는) 표기법이다. ‘점근적 상한’ 표기법이라고도 불리는데, 그 말은 최악의 경우에도 결국 이 정도의 복잡도보다 높아지지는 않음을 보장한다는 뜻이다.
즉, 위의 알고리즘의 시간 복잡도는 O(n)으로, 최악의 경우에도 a * n 의 복잡도보다 더 복잡하지는 않다.
// 입력값의 크기를 극한으로 증가시키면, 출력값에 유의미하게 영향을 주는 것은 가장 큰 차수의 항 뿐임을 기억하자.
const getAvg = numArr => {
let sum = 0; // 시간복잡도 계산에서 의미가 없다. 길이가 10000인 배열을 처리할때 이 선언문 하나 있고 없고가 차이가 있겠는가?
for (let num of numArr) {
// 여기가 시간복잡도에 영향을 주는 부분이다.
sum += num;
}
let avg = sum / numArr.length; // 마찬가지로 의미 없음.
return avg;
};
// 동적인 부분에서도 가장 차수가 큰 부분이 중요하다.
const countLoop = num => {
for (let i = 0; i < num; i++) {
console.log(i); // n 번 처리. 이래쪽과 비교하면 의미 없음.
for (let j = 0; j < num; j++) {
console.log(j); // n ^ 2 번 처리. 이곳이 시간복잡도에 영향을 주는 부분이다.
}
}
};
또한 n 이 극한으로 커진다고 가정한다면 계수 부분도 의미가 없기에, 모든 빅오 표기법은 계수가 1 인 n 차 단항으로 표현할 수 있다. 즉, 복잡도가 a*n^2 + b*n + c 라면 O(n^2)의 복잡도를 갖는 것이다.
따라서 위의 getAvg 함수는 O(n)의 시간복잡도, countLoop 함수는 O(n^2)의 시간복잡도를 갖게 된다.