시간 복잡도 (Time Complexity)

알고리즘을 작성할 때는 단순히 원하는 결과를 얻는 것뿐만 아니라, 얼마나 효율적으로 실행되는지도 함께 고려해야 한다.
이때 알고리즘의 실행 시간이 입력 데이터의 크기에 따라 어떻게 증가하는지 나타내는 개념이 시간 복잡도(Time Complexity)이다.

시간 복잡도란?

시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간을 분석하는 방법이다.

하지만 실제 실행 시간은 컴퓨터 성능, 실행 환경, 프로그래밍 언어 등에 따라 달라질 수 있다.

그래서 시간 복잡도는 실제 초 단위 시간이 아니라,
입력 데이터의 크기가 커질 때 연산 횟수가 얼마나 증가하는지를 기준으로 표현한다.

시간 복잡도를 보는 이유

데이터의 크기가 작을 때는 대부분의 알고리즘이 빠르게 실행된다.

하지만 데이터가 많아질수록 알고리즘에 따라 실행 시간이 크게 달라질 수 있다.
예를 들어 배열의 모든 값을 한 번씩 확인하는 코드는 데이터 개수만큼 반복된다.

const numbers = [10, 20, 30, 40, 50];

for (let i = 0; i < numbers.length; i++) {
  console.log(numbers[i]);
}

• 배열의 길이가 5라면 5번 반복하고, 100이라면 100번 반복한다.

이처럼 반복문이 여러 번 실행될수록 처리해야 하는 작업이 많아지고, 실행 시간도 길어질 수 있다.
따라서 알고리즘의 성능을 평가할 때는 보통 반복문이 입력 크기에 따라 얼마나 실행되는지를 중심으로 확인한다.

점근 표기법 (Asymptotic Notation)

알고리즘의 성능을 표현할 때는 점근 표기법을 사용한다.
대표적인 점근 표기법은 다음과 같다.

• Big-O
• Big-Θ
• Big-Ω

Big-Ｏ(빅오표기법)

• 알고리즘의 최악의 경우를 기준으로 시간 복잡도를 표현한다.
• 즉, 입력 데이터가 많아질 때 실행 시간이 최대 어느 정도까지 증가할 수 있는지를 나타낸다.

Big-Θ (Big-Theta·빅세타표기법)

• 알고리즘의 평균적인 증가 흐름을 표현한다.
• 즉, 최선과 최악의 경우를 함께 고려했을 때 전체적으로 어느 정도의 성능을 가지는지 나타낸다.

Big-Ω (Big-Omega)

• 알고리즘의 최선의 경우를 기준으로 성능을 표현한다.

Big-O 표기법

bigocheatsheet

Big-O 표기법은 입력 크기 n이 커질 때,
알고리즘의 실행 시간이 어떤 형태로 증가하는지 표현하는 방법이다.

대표적인 시간 복잡도는 다음과 같다.

• O(1)
• O(logn)
• O(n)
• O(nlogn)
• O(n²)
• O(2ⁿ)
• O(n!)

1. O(1) - 상수 시간

O(1)은 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 경우이다.

const numbers = [10, 20, 30, 40, 50];

console.log(numbers[0]);

배열의 첫 번째 요소에 접근하는 작업은 배열의 길이가 5개이든 100개이든 동일하다.

numbers[0];

이처럼 입력 크기와 관계없이 한 번의 작업으로 끝나는 경우를 O(1)이라고 한다.

2. O(log n) - 로그 시간

O(log n)은 입력 데이터의 크기가 커져도 실행 횟수가 천천히 증가하는 경우이다.

대표적인 예시는 이진 탐색(Binary Search)이다.

이진 탐색은 정렬된 배열에서 중간 값을 확인한 뒤,
찾는 값이 중간 값보다 작으면 왼쪽 절반만 확인하고, 크면 오른쪽 절반만 확인한다.

즉, 한 번 비교할 때마다 확인해야 할 데이터의 범위가 절반씩 줄어든다.

const numbers = [10, 20, 30, 40, 50, 60, 70];
const target = 60;

let left = 0;
let right = numbers.length - 1;

while (left <= right) {
  const mid = Math.floor((left + right) / 2);

  if (numbers[mid] === target) {
    console.log(`${target}을 찾았습니다.`);
    break;
  }

  if (numbers[mid] < target) {
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}

순차 탐색은 앞에서부터 하나씩 확인하지만, 이진 탐색은 매번 탐색 범위를 절반으로 줄인다.
그래서 데이터가 많아질수록 순차 탐색보다 효율적이다.

3. O(n) - 선형 시간

O(n)은 입력 데이터의 크기만큼 실행 시간이 증가하는 경우이다.

const numbers = [10, 20, 30, 40, 50];

for (let i = 0; i < numbers.length; i++) {
  console.log(numbers[i]);
}

배열의 길이가 5라면 5번 반복하고, 100이라면 100번 반복한다.
즉, 데이터 개수 n에 비례해서 실행 시간이 증가한다.

4. O(n log n) - 선형 로그 시간

O(n log n)은 데이터를 나누고, 나눈 데이터를 다시 처리하는 알고리즘에서 자주 나타난다.

대표적인 예시는 정렬 알고리즘이다.

• 병합 정렬
• 퀵 정렬
• 힙 정렬

const numbers = [5, 3, 8, 1, 2];

numbers.sort((a, b) => a - b);

console.log(numbers); // [1, 2, 3, 5, 8]

JavaScript의 sort()는 내부적으로 정렬 알고리즘을 사용한다.

정렬은 단순히 한 번 순회하는 것보다 복잡한 작업이기 때문에
보통 O(n log n) 형태의 시간 복잡도가 자주 등장한다.

5. O(n²) - 이차 시간

O(n²)은 반복문 안에 또 다른 반복문이 있는 경우 자주 나타난다.

const numbers = [1, 2, 3, 4];

for (let i = 0; i < numbers.length; i++) {
  for (let j = 0; j < numbers.length; j++) {
    console.log(numbers[i], numbers[j]);
  }
}

바깥 반복문이 n번 실행되고, 각 반복마다 안쪽 반복문도 n번 실행된다.
따라서 전체 반복 횟수는 다음과 같다.

n * n = n²

배열의 길이가 4라면 16번 실행되고, 100이라면 10,000번 실행된다.
이처럼 데이터가 커질수록 실행 횟수가 빠르게 증가하는 경우를 O(n²)이라고 한다.

6. O(2ⁿ) - 지수 시간

O(2ⁿ)은 입력 데이터가 하나 늘어날 때마다 경우의 수가 두 배씩 증가하는 경우이다.

대표적인 예시는 모든 부분집합을 구하는 경우이다.

const numbers = [1, 2, 3];

function getSubsets(arr) {
  const result = [[]];

  for (const value of arr) {
    const length = result.length;

    for (let i = 0; i < length; i++) {
      result.push([...result[i], value]);
    }
  }

  return result;
}

console.log(getSubsets(numbers));

배열의 길이가 3이면 부분집합은 8개이고, 4이면 16개가 된다.
즉, 데이터가 하나 늘어날 때마다 경우의 수가 두 배씩 증가한다.

7. O(n!) - 팩토리얼 시간

O(n!)은 가능한 모든 순서를 확인해야 하는 경우에 나타난다.

대표적인 예시는 모든 순열을 구하는 경우이다.

function getPermutations(arr) {
  if (arr.length === 0) return [[]];

  const result = [];

  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    const permutations = getPermutations(rest);

    for (const permutation of permutations) {
      result.push([current, ...permutation]);
    }
  }

  return result;
}

console.log(getPermutations([1, 2, 3]));

데이터가 3개라면 가능한 순서는 6개이고, 4개라면 24개가 된다.
O(n!)은 입력 크기가 조금만 커져도 실행 횟수가 매우 빠르게 증가한다.

시간 복잡도 비교

대표적인 시간 복잡도를 빠른 순서대로 정리하면 다음과 같다.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

시간 복잡도	이름	예시
O(1)	상수 시간	배열 인덱스 접근
O(log n)	로그 시간	이진 탐색
O(n)	선형 시간	배열 전체 순회
O(n log n)	선형 로그 시간	효율적인 정렬
O(n²)	이차 시간	중첩 반복문
O(2ⁿ)	지수 시간	부분집합
O(n!)	팩토리얼 시간	순열

Big-O에서 생략하는 것

Big-O 표기법은 정확한 실행 횟수를 계산하는 것이 아니라,
입력 크기가 커질 때 실행 시간이 어떤 형태로 증가하는지를 표현한다.

그래서 시간 복잡도를 계산할 때는 몇 가지 규칙이 있다.

1. 상수는 생략한다

다음 코드는 배열을 두 번 순회한다.

const numbers = [10, 20, 30, 40, 50];

for (let i = 0; i < numbers.length; i++) {
  console.log(numbers[i]);
}

for (let i = 0; i < numbers.length; i++) {
  console.log(numbers[i] * 2);
}

반복문이 두 번 있으므로 실제 실행 횟수는 2n에 가깝다.
하지만 Big-O 표기법에서는 상수를 생략해서 O(n)으로 표현한다.

O(2n) → O(n)

입력 크기가 커질수록 중요한 것은 2라는 숫자가 아니라,
데이터 개수에 비례해서 실행 시간이 증가한다는 점이기 때문이다.

2. 가장 큰 항만 남긴다

다음 코드는 배열을 한 번 순회한 뒤, 중첩 반복문을 실행한다.

const numbers = [1, 2, 3, 4];

for (let i = 0; i < numbers.length; i++) {
  console.log(numbers[i]);
}

for (let i = 0; i < numbers.length; i++) {
  for (let j = 0; j < numbers.length; j++) {
    console.log(numbers[i], numbers[j]);
  }
}

첫 번째 반복문은 O(n)이고, 두 번째 중첩 반복문은 O(n²)이다.
전체 시간 복잡도는 다음과 같이 볼 수 있다.

O(n + n²)

하지만 입력 크기가 커질수록 n²의 영향이 훨씬 커지기 때문에 가장 큰 항만 남겨 O(n²)으로 표현한다.

O(n + n²) → O(n²)

💡 예시로 이해하기

다음 식을 Big-O로 표현해보자.

• n² + 2n + 100

입력 크기 n이 커질수록 가장 큰 영향을 주는 항은 n²이다.
따라서 시간 복잡도는 다음과 같다.

• n² + 2n + 100 → O(n²)

다음 식도 마찬가지이다.

• 3n² + 100

상수 3은 생략하고, 가장 큰 항인 n²만 남긴다.

• 3n² + 100 → O(n²)

정리

시간 복잡도는 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 증가하는지 나타내는 개념이다.

실제 실행 시간을 초 단위로 계산하는 것이 아니라,
입력 데이터가 많아질 때 연산 횟수가 얼마나 증가하는지를 기준으로 판단한다.

처음에는 다음 기준으로 생각하면 된다.

• 반복문이 없으면 O(1)
• 탐색 범위가 절반씩 줄어들면 O(log n)
• 반복문이 하나면 O(n)
• 효율적인 정렬 알고리즘은 O(n log n)
• 중첩 반복문이면 O(n²)
• 경우의 수가 두 배씩 늘어나면 O(2ⁿ)
• 모든 순서를 확인하면 O(n!)

시간 복잡도를 이해하면 같은 문제를 해결하더라도 더 효율적인 알고리즘을 선택할 수 있다.