빅오 표기법과 시간 복잡도

알고리즘이란

알고리즘은 어떤 값(또는 값의 집합)을 입력으로 받아 원하는 출력으로 바꾸는 잘 정의된 계산 절차다. 계산 문제는 "입력과 출력이 어떤 관계여야 하는가"로 정의되고, 알고리즘은 그 관계를 실제로 만들어 내는 단계별 방법을 제시한다. (참고: Cormen 외, Introduction to Algorithms)

같은 문제를 푸는 알고리즘이 여러 개라면 다음 기준으로 고른다.

이 중 효율성을 기계와 상관없이 비교하는 기준이 빅오(Big O) 표기법이다. 알고리즘을 설계하고 의사 코드·순서도로 적는 과정은 컴퓨팅 사고에 있다.

시간을 직접 재면 안 되는 이유

performance.now() 같은 함수로 실행 시간을 직접 잴 수도 있다.

function addUpTo(n) {
  return n * (n + 1) / 2;
}
 
const t1 = performance.now();
addUpTo(100000000);
const t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`);

하지만 실행 시간은 기계 성능, 다른 프로세스, 런타임 최적화에 따라 매번 달라지고, 아주 빠른 코드는 차이를 측정하기조차 어렵다. 그래서 연산 횟수가 입력 크기 n에 따라 어떻게 늘어나는지를 센다.

연산 횟수 세기

// 반복문: n에 비례해 연산이 늘어난다 (대략 5n + 2번)
function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}
 
// 공식: n과 상관없이 곱셈·덧셈·나눗셈 3번
function addUpToFast(n) {
  return n * (n + 1) / 2;
}

첫 번째는 O(n), 두 번째는 O(1)이다. 정확한 횟수(5n + 2인지 3n인지)는 중요하지 않고, n이 커질 때의 증가 추세만 본다.

빅오 표기의 단순화 규칙

• 코딩 테스트와 면접에서는 보통 최악의 경우를 기준으로 빅오를 말한다. (빅오 자체는 "상한"이라는 뜻이고, 최선·평균·최악 어느 경우에나 붙일 수 있다. 아래 절 참고)
• 상수 계수는 버린다: O(2n) → O(n), O(500) → O(1)
• 최고차항만 남긴다: O(n² + 5n + 8) → O(n²)
• 산술 연산, 변수 대입, 배열 인덱스 접근, 객체 키 접근은 O(1)로 본다.
• 반복문은 (반복 횟수) × (안쪽 연산)이다. 중첩 반복문이면 곱해진다.

빅오(O)·빅오메가(Ω)·빅세타(Θ)

빅오는 점근 표기법 중 하나다. 모두 "n이 충분히 클 때 상수 배를 무시하고 비교한다"는 점은 같고, 어느 쪽에서 묶느냐가 다르다. 주로 쓰는 것은 O·Ω·Θ 셋이고, 소문자 o·ω는 같은 차수를 빼고 엄격하게 묶는 변형이다.

예를 들어 f(n) = 3n² + 5n이면

• f(n) = Θ(n²)이다. n²보다 빨리 늘지도, 느리게 늘지도 않는다.
• 상한일 뿐이므로 f(n) = O(n³)도 수학적으로는 맞지만, 정보가 적어 보통 가장 작은 상한(O(n²))을 쓴다.
• 마찬가지로 f(n) = Ω(n)도 맞지만, 가장 큰 하한은 Ω(n²)이다.
• 소문자 표기는 같은 차수를 허용하지 않는다. f(n) = o(n³)이고 ω(n)이지만, o(n²)도 ω(n²)도 아니다.

표기법과 "최선·평균·최악"은 별개의 축이다. "최악의 경우"는 어떤 입력을 기준으로 할지 고르는 것이고, O·Ω·Θ는 그렇게 정한 함수의 증가율을 위·아래·양쪽에서 묶는 방법이다. 예를 들어 삽입 정렬은

• 최악의 경우(역순 입력) Θ(n²), 최선의 경우(이미 정렬된 입력) Θ(n)
• 그래서 입력에 상관없이 말하면 실행 시간은 O(n²)이고 Ω(n)이다.

또 비교 기반 정렬은 최악의 경우 Ω(n log n)번의 비교가 반드시 필요하다는 하한이 증명되어 있다. 병합 정렬이 최악 O(n log n)이므로, 비교 정렬로는 이보다 점근적으로 빠를 수 없다는 뜻이다.

실무와 코딩 테스트에서 "이 알고리즘은 O(n log n)"이라고 할 때는 대개 최악의 경우에 대한 딱 맞는 상한, 즉 엄밀히는 Θ에 가까운 의미로 쓴다.

자주 보는 복잡도

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) 순으로 느려진다. 그래프로 그리면 O(n²)부터는 n이 조금만 커져도 거의 수직으로 치솟는다.

입력이 커질 때의 체감

선택 정렬(O(n²))과 병합 정렬(O(n log n))에 같은 입력을 넣으면 차이가 숫자로 보인다.

• O(n²)는 입력이 10배면 연산이 100배다. 중첩 반복문이 n번 안에서 다시 n번 돌기 때문이다.
• O(log n)은 입력을 두 배로 늘려도 한 단계만 는다. 반씩 나누는 횟수를 세는 것이라 8개는 3번, 16개는 4번이다. 입력이 1,000배(8 → 8,000)가 돼도 3단계가 13단계로 늘 뿐이다.
• 가능한 순열을 모두 만들어 정렬된 것을 찾는 무차별 대입(brute force) 정렬은 O(n!)이다. n = 8이면 40,320가지로, 이미 n²의 600배가 넘는다.

자료구조 연산의 복잡도

자료구조를 고를 때는 어떤 연산을 자주 하느냐를 본다. 평균과 최악이 다른 구조는 최악이 언제 오는지도 함께 기억한다.

공간은 모두 O(n)이다(스킵 리스트는 최악 O(n log n)).

정렬 알고리즘의 복잡도

최선·평균·최악, 추가 공간, 안정성을 한 표로 비교한 것은 병합 정렬과 퀵 정렬에 있다. 비교 기반 정렬은 최악 O(n log n)이 하한이고, Python sorted, Java 객체 정렬, V8의 Array.prototype.sort는 팀소트를 쓴다.

공간 복잡도

알고리즘이 추가로 사용하는 메모리가 입력 크기에 따라 어떻게 늘어나는지도 같은 방식으로 표현한다.

• 숫자, 불리언, undefined 같은 원시 값은 상수 공간 O(1)
• 문자열은 길이 n에 대해 O(n)
• 배열·객체는 원소(키) 개수 n에 대해 O(n)

예를 들어 배열의 합을 변수 하나에 누적하면 O(1) 공간, 각 원소를 두 배로 만든 새 배열을 반환하면 O(n) 공간이다.

프로그램이 쓰는 전체 공간은 고정 공간 + 가변 공간으로 나눠 볼 수 있다. 고정 공간은 코드, 단순 변수, 상수처럼 입력 크기와 상관없는 부분이고, 가변 공간은 입력 크기에 따라 달라지는 배열·동적 할당·재귀 호출 스택이다. 복잡도 분석은 가변 공간만 본다. 재귀 함수는 따로 배열을 만들지 않아도 호출 깊이만큼 스택 프레임을 쓰므로, 깊이 n인 재귀는 O(n) 공간이다.

시간과 공간의 트레이드오프

시간과 공간은 서로 맞바꿀 수 있다. 계산 결과를 저장해 두고 다시 쓰는 메모이제이션(동적 계획법)은 메모리를 더 써서 같은 계산의 반복을 없애고, 해시 테이블·트라이(기초 자료구조)는 추가 공간으로 탐색을 O(1)에 가깝게 만든다. 반대로 메모리 제한이 빡빡하면 저장 대신 매번 다시 계산한다. 코딩 테스트의 시간 제한과 메모리 제한이 각각 이 두 축이다.

입력 크기와 허용 복잡도

문제의 N 범위를 보면 허용되는 복잡도를 거꾸로 정할 수 있다. N 범위별 목표 복잡도와 떠올릴 기법 표는 코딩 테스트 접근법의 「입력 크기로 풀이 방향 정하기」에 있다.

핵심 정리

• 빅오는 입력이 커질 때의 증가율을 나타낸다. 상수와 낮은 차수 항은 무시한다.
• O는 상한, Ω는 하한, Θ는 둘 다 만족하는 딱 맞는 범위다. 최선·평균·최악은 이와 별개로 "어떤 입력을 기준으로 하느냐"다.
• 시간뿐 아니라 공간 복잡도도 같은 방식으로 따진다.
• 문제의 N 범위를 보고 허용되는 복잡도를 먼저 정하면 풀이 방향이 좁혀진다.

관련 노트: 기본 정렬, 병합 정렬과 퀵 정렬, 이분 탐색, 코딩 테스트 접근법, 컴퓨팅 사고와 개발 실력 늘리는 법