01. 빅오(Big-O) 표기법이란?

컴퓨터 과학(Computer Science) 에서 알고리즘은 어떠한 문제를 해결하기 위한 방법이고, 어떠한 문제를 해결 하기 위한 방법은 다양하기 때문에 방법(알고리즘) 간에 효율성을 비교하기 위해 빅오(big-O) 표기법을 보통 가장 많이 사용합니다.

'좋은 코드를 만든다는 것'은 어떤 의미인가?

1. 코드의 처리 속도가 더 빠를것인가? (Faster)
2. 코드가 메모리를 적게 사용하는가? (Less memory-intensive)
3. 코드가 가독성이 좋은가? (More readable)
4. 코드 줄이 짧은가?

위 4가지의 경우 전부 어느 정도 중요하다고 하지만 1-2번 이 3-4번 보다 중요합니다. (그렇다고 가독성이 개판에다가 코드가 매우 길면 좋은 코드는 아니겠지만) 그래서 빠른 처리속도와 효율적으로 메모리를 사용하면서 동시에 가독성이 좋은 코드를 짜는게 Best라고 생각합니다.

알고리즘의 시간 복잡도

알고리즘의 복잡도를 판단하는 척도로는 시간 복잡도와 공간 복잡도 두 가지가 있는데, 빅오 표기법은 시간 복잡도를 다룹니다. 당연하게도 알고리즘은 연산이 많아질수록 그 속도가 오래 걸립니다. 따라서 시간 복잡도는 알고리즘 내 연산의 횟수와 관계가 있습니다.
쉽게 말해, 연산이 많아지면 시간복잡도가 크다. 로 이해할 수 있습니다.

시간 복잡도 계산하는 방법

다양한 방법이 있겠지만 저는 가장 쉬운 방법인 timing function을 사용하겠습니다. 이것을 이용하여 알고리즘 중 어떤 알고리즘이 좀더 빠른지 계산하는 방법입니다.

모든 숫자를 더하는 함수로 예를 들어보겠습니다.

// 알고리즘: 모든 숫자 더하는 함수
function addUpToA(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
  	total += i;
  }
  return total;
}

// timing function 활용하여 시간 계산
let t1 = performance.now();
addUpToA(100000000);
let t2 = performance.now();
console.log(`걸린 시간: ${(t2 - t1) / 1000}초`)

걸린 시간: 0.09819999998807907초

매번 실행할 때마다 미세하게 다른값이 나올 수 있습니다. 매번 조금씩 다른 방식으로 연산하기 때문에 그렇습니다. 하지만 매우 작은차이기 때문에 신경안써도 됩니다. 또한, 실행되는 컴퓨터의 성능에 따라도 다를 수 있습니다. 이것도 크게 중요하지 않습니다.

여기서 중요한 것은 다양한 알고리즘의 연산속도를 비교해볼 수 있는 것입니다. 동일한 결과를 내지만 다른 방법(알고리즘)으로 짠 코드와 비교해보도록 하겠습니다.

function addUpToB(n) {
  return n * (n + 1) / 2;
}

let t1 = performance.now();
addUpToB(100000000);
let t2 = performance.now();
console.log(`걸린 시간: ${(t2 - t1) / 1000}초`)

걸린 시간: 0초 (진짜 0초는 아니고 거의 0초)

addUpToA와 addUpToB는 동일한 결과를 가져옵니다. 하지만 두 코드를 각각 실행하면 걸린시간이 addUpToB 가 훨씬 빠르다는 것을 확인할 수 있습니다. 이처럼 결과값은 동일하지만 addUpToB가 addUpToA보다 좋은 알고리즘이라는 것을 알 수 있습니다.

하지만 timing function 방식 하나로 단순히 코드비교를 할 수 있을까요? 100% 아닙니다. 그 이유에 대해서 말씀드리자면

• 기기마다 다른 방식으로 시간을 기록합니다.
• 같은 기기라도 다른 시간을 기록할 수 있습니다.
• 빠른 알고리즘의 경우 아주 짧은 시간에 처리가 되어 정확도가 떨어집니다.
• 사이즈가 너무 큰 경우, 해당 방법으로 확인하기 어렵습니다.

해당 이유때문에 실질적으로 사용하기는 어렵습니다. timing function 방식은 하나의 간단한 방법일 뿐입니다. 이러한 애로사항을 해결하기 위해 빅오 표기법을 사용하면 됩니다.

해결방법 : 빅오 표기법(big-O notation)

위의 단순 시간측정도의 문제를 해결하는 방법입니다. 빅오 표기법은 시간을 측정하기보다 컴퓨터가 처리해야 하는 연산의 개수를 세는 방법으로 측정합니다. 이런 방법은 컴퓨터의 성능에 크게 영향을 끼치지 않습니다.

빅오 표기법으로 addUpToA와 addUpToB를 비교해보겠습니다.

• addUpToA : O(n)
• addUpToB : O(1)

addUpToA은 Input의 개수가 많아질수록 for문의 연산이 늘어나기 때문에 O(n)입니다.
addUpToA은 Input의 개수가 많아져도 연산은 그대로기 때문에 O(1)입니다.

시간 복잡도 속도가 빠른 순서

시간복잡도는 다음과 같은 순서로 빠릅니다.

O(1) > O(logn) > O(n) > O(nlogn) > O(n^c) > O(c^n) > O(n!)

addUpToA는 O(n)이고, addUpToB는 O(1)이기 때문에 addUpToB이 더 빠르다고 할 수 있습니다.

빅오 표기법의 특징

빅오 표기법을 사용할 때 주의해야 하는 것이 있습니다.

• O(2) → O(1)
• O(2n) → O(n)
• O(3n^2 + 2n + 3) → O(n^2)

상수항을 없애야 하고, 하위 항들은 제거해야 됩니다.

마지막으로

어떤 문제에 대하여 알고리즘을 짜는 경우, 시간복잡도가 줄어들수록 효율적인 알고리즘을 사용한 것이기 때문에 Back-End 를 준비하는 저에게 꼭 알아야 되는 개념이라고 생각합니다.
단순히 온라인 저지에 있는 문제를 푸는 것이 아니라 이해하고 해결하는 과정이 중요하다고 생각합니다.

REFERENCE

udemy javascript algorithm