Big O — 알고리즘의 성능 표기

"이 코드는 빠른가요" 라는 물음은 환경 · 하드웨어 · 입력에 따라 답이 달라집니다. 그래서 컴퓨터 과학은 입력 크기가 커질 때 시간 (또는 메모리) 이 어떻게 자라는지를 함수 형태로 표기. 그 표기가 Big O. 이 글은 Big O 의 출자 · 자주 만나는 성장률 · 시간과 공간 복잡도 · 실무에서의 의미와 한계.

1. Big O 에 대한 이야기

표기는 1894 년 독일 수학자 Paul Bachmann 의 저서 Analytische Zahlentheorie 에 처음 등장했고, 1909 년 Edmund Landau 가 정리해 "Landau symbols" 로도 불림. 컴퓨터 과학에서는 1976 년 Donald Knuth 의 논문 "Big Omicron and big Omega and big Theta" 가 표기 관습을 정착.

자매 표기:

표기	의미
`O(f)`	상한 — 적어도 이만큼은 빠름 (실제 수행이 `c·f(n)` 이하)
`Ω(f)`	하한 — 적어도 이만큼은 느림
`Θ(f)`	정확한 차수 — 상한과 하한이 같음
`o(f)`	엄격한 상한 — 실제로 더 빠름

일상 대화에서는 거의 모두 Big O 로 부르고, 의도가 정확한 차수면 Θ 와 같이 해석.

2. 자주 만나는 성장률

표기	이름	입력 1 만 → 100 만 일 때
O(1)	상수	그대로
O(log n)	로그	약 1.3배
O(n)	선형	100배
O(n log n)	선형로그	약 130배
O(n²)	이차	1만배
O(n³)	삼차	100만배
O(2ⁿ)	지수	사실상 영원
O(n!)	팩토리얼	사실상 영원

같은 자료에 같은 작업을 해도 알고리즘 선택에 따라 100 만 배 차이가 난다는 의미.

3. 그래프

시간
 │                                                    O(2ⁿ)
 │                                       O(n²)
 │                                  ╱
 │                              ╱
 │                         ╱
 │                    ╱            O(n log n)
 │              ╱             O(n)
 │       ╱            ────
 │ ╱       ────
 │────                          O(log n)
 │═══════════════════════════   O(1)
 └─────────────────────────────  → 입력 크기 n

4. 상수 무시

Big O 는 입력이 충분히 커졌을 때의 양상을 봅니다. 상수 배수와 낮은 차수 항은 무시:

3n + 5         → O(n)
n² + n + 7     → O(n²)
1000n          → O(n)
0.001 · 2ⁿ     → O(2ⁿ)

이 단순화 덕에 대화가 짧아지지만, 실무에서는 상수가 의미를 가질 때가 있음. "O(n) 인데 상수가 1000" 과 "O(n log n) 인데 상수가 1" 은 작은 입력에서 후자가 더 빠를 수 있음.

5. 최선 · 평균 · 최악

같은 알고리즘이라도 입력에 따라 시간이 다름:

알고리즘	최선	평균	최악
선형 검색	O(1)	O(n)	O(n)
이진 검색 (정렬됨)	O(1)	O(log n)	O(log n)
퀵 정렬	O(n log n)	O(n log n)	O(n²) — 이미 정렬된 입력 등
머지 정렬	O(n log n)	O(n log n)	O(n log n)
해시 테이블 조회	O(1)	O(1)	O(n) — 충돌 폭증

운영에서는 평균보다 최악 을 보고 결정하는 경우가 많음. 사용자 한 명이라도 최악을 만나면 화면이 멎기 때문.

6. 공간 복잡도

시간 외에 메모리가 입력에 따라 어떻게 자라는지도 같은 표기로. 재귀가 깊으면 호출 스택 메모리가 같이 자라므로 시간만 보고 결정하면 OOM:

알고리즘	시간	공간
머지 정렬	O(n log n)	O(n) — 보조 배열
퀵 정렬 (in-place)	O(n log n)	O(log n) — 콜스택
동적 프로그래밍	다양	O(n) ~ O(n²) — 메모이제이션 표
메모리 효율 정렬 (heap sort)	O(n log n)	O(1)

7. 다른 길

성능을 표현하는 다른 단위:

Wall-clock time — 실제 걸린 시간 (초). 환경에 좌우.
CPU time — CPU 점유 시간.
연산 횟수 — 비교 횟수 · 메모리 접근 횟수.
벤치마크 — 같은 환경에서 두 구현을 비교.

이론과 실측의 거리가 자주 문제. CPU 캐시 · 분기 예측 · SIMD · 메모리 지역성이 Big O 가 못 잡는 자리에서 큰 차이. 운영 자리는 결국 측정해서 결정.

8. 코드를 보고 Big O 추정

// O(1) — 입력에 무관
function first(arr) { return arr[0]; }

// O(n) — 한 번 순회
function sum(arr) {
  let s = 0;
  for (const x of arr) s += x;
  return s;
}

// O(n²) — 이중 루프
function pairs(arr) {
  const out = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      out.push([arr[i], arr[j]]);
    }
  }
  return out;
}

// O(log n) — 매번 절반으로 줄임
function binarySearch(sorted, target) {
  let lo = 0, hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// O(n log n) — 정렬 + 한 번 순회
function uniqueSorted(arr) {
  return [...new Set(arr)].sort();
}

자주 쓰는 휴리스틱:

단순 한 번 루프 → O(n)
중첩 루프 → 깊이의 곱. 두 번이면 O(n²)
반복마다 절반으로 줄어드는 구조 → O(log n)
정렬을 한 번 하고 그 위에서 작업 → O(n log n)
모든 부분집합 → O(2ⁿ)
모든 순열 → O(n!)

9. 자주 걸리는 자리

근거 없는 최적화 — Knuth 의 1974 년 글 "premature optimization is the root of all evil" 이 자주 인용. 측정 없이 미리 비비 꼬는 일을 경계.

상수의 함정 — O(n) 인데 한 번의 단계가 매우 비싸면 (디스크 I / O) 같은 차수의 다른 알고리즘에 밀림.

작은 입력 vs 큰 입력 — n 이 100 정도면 어떤 차수든 비슷. n 이 100 만이 되어야 차이가 도드라짐.

메모리 우선 — 캐시 친화적인 O(n²) 가 캐시 비친화적인 O(n log n) 보다 작은 ~ 중간 입력에서 빠를 수 있음.

분할 상환 (amortized) 무시 — 동적 배열의 push 는 가끔 O(n) 이지만 평균 O(1). amortized 라고 부름. 한 번의 비싸짐을 보고 "느린 자료구조" 라 단정하면 잘못.

이론 vs 실측의 차이 — 비슷한 차수면 측정으로 결정하는 편이 정직.

하고픈 말

Big O 는 입력이 커질 때의 양상을 한 줄로 묘사하는 도구. 일상의 자료구조 선택은 이 표기 한 줄로 거의 답이 결정됨. 단 운영의 결정은 결국 측정으로 — 이론과 실측이 어긋나는 자리가 많기 때문. "premature optimization is the root of all evil" 의 인용이 여기서 살아 있는 자리.

design-patterns
oop-vs-functional

Donald Knuth Big Omicron and big Omega and big Theta (1976) · The Art of Computer Programming · Knuth Structured Programming with go to Statements (1974) · Introduction to Algorithms (CLRS) · MIT 6.006 · Big-O Cheat Sheet · VisuAlgo · Wikipedia Big O notation 을 참고합니다.

Big O — 알고리즘의 성능 표기

1. Big O 에 대한 이야기

자매 표기:

표기	의미
`O(f)`	상한 — 적어도 이만큼은 빠름 (실제 수행이 `c·f(n)` 이하)
`Ω(f)`	하한 — 적어도 이만큼은 느림
`Θ(f)`	정확한 차수 — 상한과 하한이 같음
`o(f)`	엄격한 상한 — 실제로 더 빠름

일상 대화에서는 거의 모두 Big O 로 부르고, 의도가 정확한 차수면 Θ 와 같이 해석.

2. 자주 만나는 성장률

표기	이름	입력 1 만 → 100 만 일 때
O(1)	상수	그대로
O(log n)	로그	약 1.3배
O(n)	선형	100배
O(n log n)	선형로그	약 130배
O(n²)	이차	1만배
O(n³)	삼차	100만배
O(2ⁿ)	지수	사실상 영원
O(n!)	팩토리얼	사실상 영원

같은 자료에 같은 작업을 해도 알고리즘 선택에 따라 100 만 배 차이가 난다는 의미.

3. 그래프

시간
 │                                                    O(2ⁿ)
 │                                       O(n²)
 │                                  ╱
 │                              ╱
 │                         ╱
 │                    ╱            O(n log n)
 │              ╱             O(n)
 │       ╱            ────
 │ ╱       ────
 │────                          O(log n)
 │═══════════════════════════   O(1)
 └─────────────────────────────  → 입력 크기 n

4. 상수 무시

Big O 는 입력이 충분히 커졌을 때의 양상을 봅니다. 상수 배수와 낮은 차수 항은 무시:

3n + 5         → O(n)
n² + n + 7     → O(n²)
1000n          → O(n)
0.001 · 2ⁿ     → O(2ⁿ)

5. 최선 · 평균 · 최악

같은 알고리즘이라도 입력에 따라 시간이 다름:

알고리즘	최선	평균	최악
선형 검색	O(1)	O(n)	O(n)
이진 검색 (정렬됨)	O(1)	O(log n)	O(log n)
퀵 정렬	O(n log n)	O(n log n)	O(n²) — 이미 정렬된 입력 등
머지 정렬	O(n log n)	O(n log n)	O(n log n)
해시 테이블 조회	O(1)	O(1)	O(n) — 충돌 폭증

운영에서는 평균보다 최악 을 보고 결정하는 경우가 많음. 사용자 한 명이라도 최악을 만나면 화면이 멎기 때문.

6. 공간 복잡도

시간 외에 메모리가 입력에 따라 어떻게 자라는지도 같은 표기로. 재귀가 깊으면 호출 스택 메모리가 같이 자라므로 시간만 보고 결정하면 OOM:

알고리즘	시간	공간
머지 정렬	O(n log n)	O(n) — 보조 배열
퀵 정렬 (in-place)	O(n log n)	O(log n) — 콜스택
동적 프로그래밍	다양	O(n) ~ O(n²) — 메모이제이션 표
메모리 효율 정렬 (heap sort)	O(n log n)	O(1)

7. 다른 길

성능을 표현하는 다른 단위:

Wall-clock time — 실제 걸린 시간 (초). 환경에 좌우.
CPU time — CPU 점유 시간.
연산 횟수 — 비교 횟수 · 메모리 접근 횟수.
벤치마크 — 같은 환경에서 두 구현을 비교.

이론과 실측의 거리가 자주 문제. CPU 캐시 · 분기 예측 · SIMD · 메모리 지역성이 Big O 가 못 잡는 자리에서 큰 차이. 운영 자리는 결국 측정해서 결정.

8. 코드를 보고 Big O 추정

// O(1) — 입력에 무관
function first(arr) { return arr[0]; }

// O(n) — 한 번 순회
function sum(arr) {
  let s = 0;
  for (const x of arr) s += x;
  return s;
}

// O(n²) — 이중 루프
function pairs(arr) {
  const out = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      out.push([arr[i], arr[j]]);
    }
  }
  return out;
}

// O(log n) — 매번 절반으로 줄임
function binarySearch(sorted, target) {
  let lo = 0, hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// O(n log n) — 정렬 + 한 번 순회
function uniqueSorted(arr) {
  return [...new Set(arr)].sort();
}

자주 쓰는 휴리스틱:

단순 한 번 루프 → O(n)
중첩 루프 → 깊이의 곱. 두 번이면 O(n²)
반복마다 절반으로 줄어드는 구조 → O(log n)
정렬을 한 번 하고 그 위에서 작업 → O(n log n)
모든 부분집합 → O(2ⁿ)
모든 순열 → O(n!)

9. 자주 걸리는 자리

근거 없는 최적화 — Knuth 의 1974 년 글 "premature optimization is the root of all evil" 이 자주 인용. 측정 없이 미리 비비 꼬는 일을 경계.

상수의 함정 — O(n) 인데 한 번의 단계가 매우 비싸면 (디스크 I / O) 같은 차수의 다른 알고리즘에 밀림.

작은 입력 vs 큰 입력 — n 이 100 정도면 어떤 차수든 비슷. n 이 100 만이 되어야 차이가 도드라짐.

메모리 우선 — 캐시 친화적인 O(n²) 가 캐시 비친화적인 O(n log n) 보다 작은 ~ 중간 입력에서 빠를 수 있음.

이론 vs 실측의 차이 — 비슷한 차수면 측정으로 결정하는 편이 정직.

하고픈 말

design-patterns
oop-vs-functional

Big O — 알고리즘의 성능 표기

Big O — 알고리즘의 성능 표기

1. Big O 에 대한 이야기

2. 자주 만나는 성장률

3. 그래프

4. 상수 무시

5. 최선 · 평균 · 최악

6. 공간 복잡도

7. 다른 길

8. 코드를 보고 Big O 추정

9. 자주 걸리는 자리

하고픈 말

Next

programming 카테고리의 다른 글

Big O — 알고리즘의 성능 표기

Big O — 알고리즘의 성능 표기

1. Big O 에 대한 이야기

2. 자주 만나는 성장률

3. 그래프

4. 상수 무시

5. 최선 · 평균 · 최악

6. 공간 복잡도

7. 다른 길

8. 코드를 보고 Big O 추정

9. 자주 걸리는 자리

하고픈 말

Next

programming 카테고리의 다른 글