빅오 표기법 (Big-O Notation)

목표

• 빅오 표기법의 필요성
• 빅오 표기법이 무엇인지
• 빅오 표기법의 간단한 표현법
• 시간복잡도와 공간복잡도의 정의
• 빅오 표기법을 이용한 알고리즘 표기법
• 로그(log)가 무엇인지

빅오 표기법의 필요성

어떤 문제를 해결하는 두 가지 방법이 있을 때, 하나는 루프를 사용하고, 다른 하나는 리스트나 문자열을 사용하는 방법일 수 있습니다. 무엇이 더 나은지 알기 위해서는 빅오 표기법이 필요합니다. 빅오 표기법을 사용하면 코드를 일반화하고 비교하며 성능을 평가할 수 있는 시스템을 제공합니다.

 

예시

1부터 N까지 모든 숫자를 더하는 함수를 예로 들어보겠습니다. 

// 첫 번째 방법: 루프 사용
function addUpTo(n) {
  let total = 0;
  for (let i = 0; i <= n; i++) {
    total += i;
  }
  return total;
}

// 두 번째 방법: 수학적 공식 사용
function addUpTo(n) {
  return (n * (n + 1)) / 2;
}

어떤 방법이 더 나을까요?

• 어떤 것이 더 빠를까요?
• 어떤 것이 더 적은 메모리를 사용할까요?
• 어떤 것이 더 읽기 쉬울까요?

성능 평가 방법

우선, 코드가 얼마나 빠른지를 설명할 때는 아래와 같이 평가할 수 있습니다.

let t1 = performance.now();
addUpTo(100000000);
let t2 = performance.now();
console.log(`Time: ${(t2 - t1) / 1000} seconds`);

 

동일한 작업을 하지만 두 번째 코드가 훨씬 빠릅니다. 그러나 performance.now()로 두 시간을 단순히 빼는 것은 불확실하고 완전히 믿을 수 없습니다. 기계마다, 매번 실행할 때마다 결과가 달라질 수 있습니다.

그렇다면 코드 실행 시간을 재는 것보다 컴퓨터가 처리해야 하는 연산 갯수를 세면 됩니다.

 

예를 들어

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

위 코드는 * 연산 1번, + 연산 1번, / 연산 1번, 총 3번의 연산이 이루어집니다.

 

하지만

function addUpTo(n) {
  let total = 0;
  for (let i = 0; i <= n; i++) {
    total += i;
  }
  return total;
}

 

이 함수는 대충 5n + 2 만큼 연산이 일어납니다.

• 초기화(let total = 0): 1번
• 변수 선언(let i = 0): 1번
• 비교 연산(i <= n): n번 (루프가 n+1번 돌아가므로)
• 증가 연산(i++): n번 및 n번 선언
• 덧셈 연산(total += i): n번

이런식으로 연산을 모두 세는건 쉽지 않은 작업이다.

 

중요한 점은 N이 커질수록 연산의 갯수도 N만큼 늘어난다는 점입니다. 전체적인 추세가 중요합니다.

 

빅오는 대략적으로 연산의 수를 세는 것에 붙인 공식적인 표현입니다. 입력된 내용이 늘어날수록 알고리즘의 실행 시간이 어떻게 변하는지 설명하는 공식적인 방식입니다. 빅오는 입력 크기와 실행 시간의 관계를 나타냅니다. 일반적으로 가장 높은 실행 시간 값들을 나타냅니다.

 

빅오 표기법의 간단한 표현법

• O(1): 상수 시간 (입력 크기에 관계없이 일정한 시간)
• O(log n): 로그 시간 (입력 크기가 커질수록 시간이 느리게 증가)
• O(n): 선형 시간 (입력 크기에 비례하여 시간 증가)
• O(n log n): 로그 선형 시간 (예: 퀵 정렬)
• O(n^2): 이차 시간 (입력 크기의 제곱에 비례하여 시간 증가)
• O(2^n): 지수 시간 (입력 크기에 따라 시간 폭발적으로 증가)
• O(n!): 팩토리얼 시간 (입력 크기에 따라 시간 급격히 증가)

시간복잡도 그래프

 

1. 산술 연산은 상수입니다. N의 값에 관계없이 일정한 시간입니다. (예: 2 + 2, 1000000 + 2)
2. 변수에 값을 저장하는 것은 별다른 시간 차이가 없습니다. (예: x = 100, x = 100000)
3. 배열에서 인덱스를 사용하거나 객체에서 키를 사용해서 찾는 것은 상수 시간입니다.
4. 루프가 있으면 복잡도가 루프의 길이와 안에 있는 연산의 곱이 됩니다. for문을 사용해서 배열을 처리할 경우 O(n)입니다.
5. 루프 중첩이 있다면 O(n^2)입니다.

 

시간 복잡도와 공간 복잡도

지금까지는 시간과 관련된 부분을 걱정했습니다. 이를 시간 복잡도(Time Complexity)라고 합니다. 이제는 입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지하는지에 대해서 얘기해보겠습니다. 이를 공간 복잡도(Space Complexity)라고 합니다.

공간 복잡도는 알고리즘이 사용하는 메모리의 양을 나타냅니다. 이는 주로 두 가지 요소로 구성됩니다:

• 고정 공간 (Fixed Space): 알고리즘이 사용하는 상수 공간입니다. 예: 함수 내에서 선언되는 변수들
• 가변 공간 (Variable Space): 알고리즘의 입력 크기에 따라 달라지는 공간입니다. 예: 동적으로 할당되는 배열이나 리스트

예시를 통해 공간 복잡도를 살펴보겠습니다.

// O(1) 공간 복잡도: 고정 공간만 사용
function addUpTo(n) {
  return (n * (n + 1)) / 2;
}

위 함수는 입력 크기와 상관없이 일정한 공간만을 사용합니다. 따라서 공간 복잡도는 O(1)입니다.

 

// O(n) 공간 복잡도: 가변 공간 사용
function createArray(n) {
  let arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(i);
  }
  return arr;
}

 

위 함수는 입력 크기 n에 비례하여 배열을 생성합니다. 따라서 공간 복잡도는 O(n)입니다.

공간 복잡도는 알고리즘의 효율성을 평가하는 데 중요한 요소입니다. 입력 크기가 커질수록 알고리즘이 사용하는 메모리가 어떻게 변하는지 이해하면, 더 효율적인 알고리즘을 설계할 수 있습니다.

 

로그(log)란?

로그는 특정 숫자를 몇 번 곱해야 다른 숫자가 되는지를 나타내는 수학적 개념입니다. 예를 들어, log2(8) = 3은 2를 몇 번 곱해야 8이 되는지를 나타냅니다. 로그 시간 복잡도는 이와 같이 큰 문제를 작은 문제로 나누는 알고리즘에서 주로 나타납니다. 예: 이진 탐색은 로그 시간 복잡도를 가집니다.