비용이 어떻게 증가하는가

Big O는 입력이 커짐에 따라 비용이 얼마나 증가하는지를 측정합니다. 상수 계수가 아니라, 증가율입니다. N=100에서 둘 다 ‘몇 밀리초’ 안에 끝나는 두 알고리즘이라도, 하나가 O(N)이고 다른 하나가 O(N²)라면 N=10,000에서는 10,000배 차이가 날 수 있습니다.

일반적인 복잡도 클래스

O(1) — 상수 시간. N과 관계없이 비용이 동일합니다. 예: 키로 해시 테이블 조회, 인덱스로 배열 접근, 스택 push/pop. N을 두 배로 늘려도 비용은 변하지 않습니다.

O(log N) — 로그. 각 단계마다 남은 작업이 절반으로 줄어듭니다. 예: 정렬된 배열에서의 이진 탐색, 게임 엔진의 BVH 공간 쿼리, 균형 이진 트리 연산. N=1,000,000일 때: log₂(1,000,000) ≈ 20 단계.

O(N) — 선형. 입력 크기에 비례하여 비용이 증가합니다. 예: 리스트의 선형 탐색, 파일 읽기, 컬렉션 내 항목 개수 세기. N=10,000일 때: 10,000회 연산.

O(N log N) — 선형 로그. 거의 선형이지만 약간 더 나쁩니다. 예: 병합 정렬, 효율적인 최단 경로 알고리즘 (힙을 사용한 다익스트라). N=10,000일 때: 약 133,000회 연산.

O(N²) — 제곱. 비용이 폭발적으로 증가합니다. 예: 동일한 리스트를 순회하는 루프 안에서 list.contains() 호출, 버블 정렬, 단순한 모든 쌍 비교. N=1,000일 때: 1,000,000회 연산. N=10,000일 때: 100,000,000회 연산.

O(2^N) — 지수. 의미 있는 규모에서는 사용할 수 없다. 예: 조합적 무차별 대입, 모든 부분집합 찾기. N=30일 때: 10억 회 이상의 연산.

보이게 만드는 규모

N=10 비교:
O(N):   10
O(N²):  100
비율:  10x

N=1,000 비교 횟수:
O(N):   1,000
O(N²):  1,000,000
비율:  1,000x

N=10,000 비교 횟수:
O(N):   10,000
O(N²):  100,000,000
ratio:  10,000x

N=10에서는 차이가 거의 드러나지 않습니다. N=10,000에서는 O(N²) 알고리즘이 10,000배 더 느리게 실행됩니다. 이것이 MOAD-0001이 수십 년 동안 눈에 띄지 않았던 이유입니다. 1993년에는 50개의 노드를 가진 그래프에서 실행되었지만, 2020년에는 동일한 코드가 50,000개의 노드를 가진 의존성 그래프에서 실행되었습니다.

세 가지 연산 분류하기

복잡도 클래스를 구체적인 연산에 적용하세요. 각 연산에 대한 핵심 질문은 N이 커질수록 연산 횟수가 얼마나 증가하는가입니다.

올바른 코드, 잘못된 성장 곡선

O(N²) 시간 복잡도로 실행되는 올바른 코드는 O(N) 코드와 동일한 결과를 생성한다. 테스트는 통과하고, 출력은 일치하며, 예외도 발생하지 않는다. 결함은 성장 곡선 속에 숨겨져 있다.

이 특성 때문에 O(N²) 결함은 퇴적성이다. 즉, 동작하는 코드 안에 굳어 있다가 N이 특정 임계값을 넘을 때만 드러난다. 코드는 변경되지 않았다. 코드 주변의 세상이 바뀐 것이다.

MOAD-0001: 퇴적 결함

가장 흔한 사례: 그래프 순회 루프 안에 visited = []를 두는 경우입니다.

visited = []
for node in graph:
if node not in visited:  # O(N) scan each call
visited.append(node)
process(node)

각 not in visited 호출은 0부터 len(visited)-1까지의 항목을 스캔합니다. N번의 호출 × 평균 N/2개 항목 스캔 = 총 O(N²). 해결책: 한 줄.

visited = set()  # O(1) 멤버십 테스트
for node in graph:
if node not in visited:  # O(1) 해시 조회
visited.add(node)
process(node)

동일한 동작. 동일한 출력. 동일한 테스트 통과. 성장률이 O(N²)에서 O(N)으로 바뀝니다. N=1,000일 때: 1,000배 더 빠름. N=10,000일 때: 10,000배 더 빠름.

해밍 시대가 이를 만든 이유

초기 Java와 C에서는 ArrayList(동적 배열)가 기본 순차 컨테이너였습니다. Set도 존재했지만 관용적이지 않았고, 개발자들은 익숙한 것을 선택했습니다. 1993년 N=50 규모의 그래프 순회에서 visited = []를 사용하면 마이크로초 단위로 실행됐습니다. 그 코드는 버전 관리에 들어가 복사되고, 라이브러리로 감싸지고, 패키지 매니저로 배포됐습니다. 2020년에는 동일한 패턴이 50,000개 노드의 의존성 그래프에서 실행됐습니다.

1993년에는 코드가 올바랐습니다. 세상이 바뀌면서 비용이 커진 것입니다. 해밍 시대는 성장률 질문을 명확히 하지 않음으로써 이런 종류의 결함을 남겼습니다.

진단 및 수정

진단을 적용하세요: O(N²) 패턴을 찾아 수정 방법을 확인하세요.

어떤 명명 변경

Big O라는 이름이 생기기 전, 프로그래머들은 '이 코드는 느리게 실행된다'는 점을 알아차렸습니다. 그들은 프로파일링을 하고 코드를 다시 작성했습니다. 그러나 그들은 패턴을 가르칠 수 없었고, 단지 사례를 지적할 수밖에 없었습니다. 이름 없는 패턴은 전파될 수 없습니다.

Big O라는 이름이 생긴 후, 선임 엔지니어는 '이것은 O(N²)이므로 세트로 교체하세요'라고 말할 수 있었고, 주니어 엔지니어는 그 패턴을 이해하고 적용하며 다시 가르칠 수 있게 되었습니다. 이름 덕분에 패턴이 지식의 전달 가능한 단위가 되었습니다.

해밍은 다른 분야에서도 이 역학을 알고 있었습니다. 그는 1960년대에 '스파게티 코드'라는 이름을 붙임으로써, 모두가 경험했지만 아무도 이름 붙이지 못했던 결함의 한 부류를 커뮤니티가 인식하고 논의하며 결국 제거할 수 있게 되었다고 설명했습니다. 동일한 메커니즘이 복잡도 클래스에도 적용됩니다.

Unhamming은 해밍이 생략한 어휘를 추가합니다: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). 이 이름들은 읽는 코드에서 성장 곡선을 보고, 규모에 따른 성능을 예측하며, 수정 사항을 정확히 전달할 수 있게 해줍니다. 이들은 해밍이 말한 기본 개념의 기준 — 지속 가능하며, 나머지 분야의 대부분을 생성할 수 있는 — 을 충족합니다. [TITLE who_coined_big_o/]

From Number Theory to Computer Science

Big O notation은 컴퓨터 과학에서 시작되지 않았습니다. 순수 수학, 특히 수론에서 시작되었으며, Donald Knuth가 알고리즘에 적용하기 74년 전입니다.

Paul Bachmann, 1894

독일 수학자 Paul Bachmann은 1894년 저서 Die Analytische Zahlentheorie (Analytic Number Theory)에서 O 표기법을 처음 소개했습니다. 그는 한 양이 다른 양보다 상수 배 이상 빠르게 증가하지 않는다는 것을 간결하게 표현할 방법이 필요했습니다. 'f(n) = O(g(n))'라고 쓰면, f는 g보다 빠르게 증가하지 않는다는 의미가 됩니다. 이를 통해 수론학자들은 근사의 오차항을 다룰 때 정확한 상수를 추적하지 않고도 추론할 수 있었습니다.

Bachmann은 루프, 데이터 구조, 실행 시간을 생각하지 않았습니다. 그는 소수 분포, 특히 Prime Number Theorem의 오차항에 대해 생각하고 있었습니다.

Edmund Landau, 1909

또 다른 독일 수학자 Edmund Landau는 1909년 저서 Handbuch der Lehre von der Verteilung der Primzahlen (Handbook on the Distribution of Prime Numbers)에서 이 표기법을 널리 알렸습니다. Landau는 관련 표기법인 o (little-o)도 도입했으며, 이 점근 표기법들을 광범위하게 사용한 덕분에 이 표기법들은 Bachmann-Landau notation 또는 간단히 Landau notation으로 불리게 되었습니다.

60년 동안 O 표기법은 수학 분야에만 존재했습니다. 어떤 프로그래머도 이를 생각하지 않았습니다.

도널드 커누스, 1968 & 1976

도널드 커누스는 이 표기법을 컴퓨터 과학으로 옮겨왔습니다. 《The Art of Computer Programming》(Vol. 1, 1968)에서 커누스는 알고리즘의 실행 시간을 설명하기 위해 O 표기법을 사용했습니다. 이는 바흐만의 도구를 새로운 영역으로 직접 이식한 것이었습니다. 그는 알고리즘 분석에 이 표기법을 체계적으로 적용한 최초의 인물이었습니다.

1976년, 커누스는 SIGACT News에 ‘Big Omicron and Big Omega and Big Theta’라는 제목의 짧은 논문을 발표했습니다. 그는 하한을 위한 Omega(Ω)와 엄밀한 경계를 위한 Theta(Θ)를 도입하여, 오늘날 컴퓨터 과학에서 사용하는 세 가지 기호 체계를 완성했습니다. 또한 그는 이 기호들의 사용을 분야 전반에 걸쳐 표준화할 것을 주장했습니다. 이는 의도적인 표준화 조치였으며, 이로 인해 해당 표기법의 채택이 가속화되었습니다.

1980년대 초반까지 Big O는 모든 알고리즘 교과서에 등장했습니다. 1990년대에는 표준 면접 용어가 되었습니다.

74년의 여정

1894 — 바흐만이 수론에서 O를 도입하다
1909 — 란다우가 O, o 및 전체 표기법 체계를 대중화하다
1953 — Hamming이 Bell Labs에서 연구를 시작함 (Big O를 CS 도구로 배우지 못함)
1968 — Knuth가 TAOCP Vol. 1에서 알고리즘 분석에 O를 적용함
1976 — Knuth가 Omega와 Theta를 추가하고 표준화를 주장함
1980s — Big O가 모든 CS 커리큘럼에 포함됨
1993 — MOAD-0001 퇴적층이 프로덕션 코드에 형성됨
1995 — Hamming이 마지막으로 강의를 진행함; Big O를 다루지 않음
2026 — MOAD-0001이 1,000개 이상의 오픈소스 프로젝트에서 발견됨

Bachmann의 도구는 74년 동안 순수 수학 분야에 머물렀습니다. 모든 수학자에게는 보였지만, 모든 프로그래머에게는 보이지 않았습니다. Knuth는 이를 이식할 수 있음을 알아보았습니다. 같은 시대에 같은 컴퓨팅 커뮤니티와 협력했던 Hamming은 이를 자신의 강의에 포함시키지 않았습니다.

Knuth의 표준화가 중요했던 이유 [BLOCK_TYPE SECTION/STEP]

Knuth의 1976년 논문은 Omega와 Theta를 소개하는 것 이상의 일을 했습니다. 그는 해당 분야에 일관된 표기법이 필요하며, 일관되지 않은 표기법이 실제로 해를 끼친다고 주장했습니다. 서로 다른 교과서에서 O를 서로 다른 의미로 사용했습니다. 때로는 상한으로, 때로는 근사치로, 때로는 상수가 중요한지 여부를 명시하지 않고 사용했습니다. Knuth는 이를 정리했습니다. [BLOCK_TYPE SECTION/STEP]

이는 Hamming의 패턴-명명 동역학을 표기법 자체에 적용한 것입니다. Knuth가 기호를 표준화하기 전에는 엔지니어들이 교과서, 논문, 팀 간에 복잡도 주장을 정확하게 전달할 수 없었습니다. 표준화 이후에는 '이 알고리즘은 O(N log N)으로 실행된다'는 표현이 누가 말하든 정확히 하나의 의미를 갖게 되었습니다. [BLOCK_TYPE SECTION/STEP]

Knuth는 또한 비공식적인 해석을 제공했습니다: 'O(f(n))은 충분히 큰 모든 n에 대해 실행 시간이 f(n)의 상수 배 이하라는 의미입니다.' 이 해석 — 상한, 상수 인자까지, 큰 입력에 대해 — 은 모든 프로그래머가 배우는 표준 직관이 되었습니다.