[알고리즘] Big-O 표기법
Big-O 표기법은, '좋은', '그저 그런', '엉망인' 등의 주관적인 표현법 대신, 숫자로 코드의 성능을 표기할 수 있다.
때로는 코드가 작동하기만 하면 충분하다고 생각할 수 있지만, 우리가 정량화된 측정도구인 Big-O 표기법을 사용하는 이유는 무엇일까?
Big-O 표기법의 필요성
- 수천개의 데이터가 있는 큰 데이터셋을 다룰 때, 한 알고리즘이 다른 알고리즘보다 실행하는데 한시간이 더 빠르다면 성능을 중요시 해야한다.
- 해결책이 만족스럽다고 해도, 다른 해결책과 비교하고 성능이 어떤지 이해하는 것은 성장에 도움이 된다.
- 여러 접근법의 장단점을 얘기할 때도 유용하다. 어떤 해결책은 많은 데이터량을 잘 다룰 수 있고, 다른 하나는 더 오랜 시간이 걸리지만, 데이터값이 달라질 때 변동량이 적을 수 있다.
- 디버깅을 할 때 코드가 느려지는 이유를 찾는 데 유용하다. 코드가 작동하지만, 생각보다 오랜 시간이 걸리고 브라우저에서 함수를 실행했을 때, 컴퓨터가 렉이 걸린다면 문제를 야기할 것이다.
즉, Big-O를 이해하면 어디서 문제가 나타나는지 찾기 수월해지고, 비효율적인 코드를 찾는 데에 도움이 된다.
코드 측정법
코드 시간 재기
1부터 n까지 수를 더하는 두 방식의 코드가 있다.
add_up_to_slower.js
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.`) //시간의 차 = 함수 실행에 걸리는 시간add_up_to_faster.js
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.`)이 두 코드의 실행시간을 비교하면 어떤 코드가 더 오래 걸리는지 확인할 수 있다.
그러나 이렇게 수동으로 시간을 구하고, 서로 비교하는 것이 가장 좋은 방법은 아니다. 어째서일까?
코드 시간 측정의 단점
- 각자 다른 컴퓨터에서 다른 시간이 기록될 수 있다. (컴퓨터 자체의 성능이 다를 경우)
- 같은 컴퓨터에서도 종종 다른 시간이 기록될 수 있다.(실행되는 환경에는 변인이 존재한다.)
- 실행 시간이 아주 빠른 알고리즘을 비교하기가 어렵다.
예를 들어 한 코드가 한 시간이 걸리고, 다른 코드가 네 시간이 걸린다고 가정해보자. 어떤 코드가 빠른지 알기 위해 테스트를 실행하면 어느 세월에 전부 끝낼 수 있을까?
이렇게 하지 않아도, 코드를 비교할 수 있는 특정한 값이 있다면 좋을 것이다. 이 때, 빅오 표기법이 유용하다.
연산 갯수 세기 - Big-O 표기법
코드가 실행될때 걸리는 정확한 시간을 초로 측정하는것 대신에, 컴퓨터가 처리해야하는 연산 갯수를 센다.
add_up_to_faster.js
이 코드의 경우 곱하기 연산, 더하기 연산, 나눗셈 연산, 총 3번 연산이 이루어진다.
add_up_to_slower.js
그러나 반복문을 사용하는 이 코드는 n번 동안 실행되는 연산이 5개가 존재하고, 한번씩 할당하는 연산이 두 개가 존재한다. 이를 대략 5N+2로 표현할 수 있겠지만, 이건 너무 복잡하다.
우리에게 중요한 것은 전체적인 추세를 보는 것이다.
add_up_to_faster.js
연산 횟수가 상수(3회)인 함수를 많이 실행하면, 아주 빠르게 실행되고, 연산 횟수가 늘어난다고 해서 일정한 증가폭을 보이지 않는다. 아주 많이 이 함수를 실행하면, 연산횟수가 1회인 함수와 그래프가 크게 다르지 않을 것이다.
따라서 O(1)로 표현한다.
add_up_to_slower.js
연산 횟수가 5N+2였던 함수를 확인해보자. 그래프는 N에 비례해서 늘어나고 있다. 가장 영향을 미치는 수는 N이다. 그렇기 때문에 5n이든 그냥 n이든 크게 상관하지 않는다. 대략적으로는 추세가 비슷하기 때문이다.
즉 O(N)으로 표현한다.
결론적으로, Big-O 표기법은 연산 횟수에 의존하며, 그 중에서도 입력 크기 N에 따라 결정된다.