알고리즘 수업에서 가장 먼저 배우는 공식 같은 말이 있죠. '다항 시간이면 효율적, 지수 시간이면 비효율적.' O(n²)은 괜찮고 O(2ⁿ)은 큰일 난다는 그 감각이요. 그런데 이 상식이 정말 맞을까요? Ben Recht의 블로그 argmin에 올라온 이 글이 바로 이 질문을 던져요. 글 주소에 있는 'Galactus'는 마블 코믹스에서 행성을 통째로 집어삼키는 존재인데요, 이론상으로는 최고지만 현실에서는 쓸 수 없는 은하 알고리즘(galactic algorithm)을 가리키는 말장난이에요.
빅오 표기법이 숨기는 것
빅오(Big-O) 표기법은 입력이 한없이 커질 때 실행 시간이 어떻게 늘어나는지만 봐요. 그래서 앞에 붙는 상수가 얼마나 큰지, 차수가 얼마나 높은지는 따지지 않죠. 문제는 여기서 생겨요.
간단히 계산해볼게요. n이 1,000일 때 n¹⁰⁰은 10³⁰⁰이고, 2ⁿ은 약 10³⁰¹이에요. 앞의 것은 '다항 시간'이라 효율적이라고 하고, 뒤의 것은 '지수 시간'이라 비효율적이라고 하죠. 하지만 실제로는 둘 다 우주의 수명이 다할 때까지 끝나지 않아요. 이론의 분류와 현실의 체감이 완전히 어긋나는 거예요.
실제로 있는 은하 알고리즘들
머릿속 장난처럼 들리지만 실제 사례가 꽤 많아요.
- 행렬 곱셈: 교과서에 나오는 방식은 O(n³)이에요. 1969년 슈트라센이 O(n^2.81) 알고리즘을 내놨는데, 이건 실제로도 일부 쓰여요. 그 뒤로 연구자들이 지수를 2.37대까지 끌어내렸지만, 이 알고리즘들은 숨은 상수가 너무 커서 현실적인 크기의 행렬에서는 오히려 느려요. 그래서 NumPy가 쓰는 BLAS 같은 라이브러리는 여전히 O(n³) 방식을 하드웨어에 맞춰 극한까지 최적화해서 써요.
- 정수 곱셈: 2019년 하비(Harvey)와 반 데르 회번(van der Hoeven)이 O(n log n) 알고리즘을 증명했어요. 이론적으로는 기념비적인 결과인데, 이 알고리즘이 효과를 내려면 숫자가 상상도 못 할 만큼 커야 해서 실제로 쓸 곳은 거의 없어요.
- 소수 판정: 2002년 AKS 알고리즘이 결정론적인 다항 시간 소수 판정이 가능하다는 걸 처음으로 보였어요. 하지만 실제 암호 라이브러리는 확률적 방법인 밀러-라빈 테스트를 써요. 훨씬 빠르고, 틀릴 확률은 무시해도 될 만큼 작거든요.
지수 시간 가설(ETH)은 또 뭐냐면
지수 시간 가설(Exponential Time Hypothesis)은 1999년 임팔리아초(Impagliazzo)와 파투리(Paturi)가 제안했어요. 쉽게 말하면, 대표적인 어려운 문제인 3-SAT은 변수 개수 n에 대해 2ⁿ 수준보다 근본적으로 빠르게 풀 수 없다는 주장이에요. P≠NP보다 한 발 더 나간, 더 강한 가정이죠.
이 가설이 쓸모 있는 건 '더 빠른 방법은 찾지 않아도 돼요'라는 신호를 줄 수 있어서예요. 예를 들어 diff 도구나 맞춤법 검사에 쓰이는 편집 거리(edit distance) 문제는 보통 O(n²) 동적 프로그래밍으로 풀어요. 2015년 연구에서는 이걸 O(n^(2-ε))보다 빠르게 풀 수 있다면 ETH를 더 강하게 만든 버전(SETH)이 깨진다는 걸 보였어요. 이렇게 문제들의 난이도를 촘촘하게 연결해 비교하는 분야를 세밀 복잡도(fine-grained complexity)라고 해요.
이론은 길을 잃은 걸까
이 글의 문제의식은 이론 컴퓨터 과학이 '효율적'이라는 단어를 실제 계산과 점점 동떨어진 뜻으로 쓰게 된 게 아니냐는 거예요. 아무도 실행하지 않을 알고리즘의 지수를 0.001 줄이는 연구를 정말 '효율'에 대한 연구라고 할 수 있냐는 거죠.
물론 반론도 있어요. 처음엔 쓸모없던 다항 시간 알고리즘이 나중에 다듬어져 실용화된 경우도 있거든요. 선형계획법의 타원체법은 실전에서 느렸지만, 그 뒤에 나온 내부점법은 지금 상용 최적화 솔버의 핵심이 됐어요. 이론의 돌파구가 실용적인 돌파구로 이어지기도 하는 거죠. 결국 중요한 건 이론에서 말하는 효율과 현실에서 말하는 효율을 혼동하지 않는 것이에요.
한국 개발자에게 주는 시사점
코딩 테스트를 준비하면서 빅오에 익숙해진 분이 많을 텐데요, 실무에서 빅오는 출발점일 뿐이에요. 실제로 파이썬의 Timsort나 여러 C++ 표준 라이브러리 구현의 정렬은 작은 구간에서 O(n²)인 삽입 정렬을 섞어 써요. n이 작을 땐 그게 더 빠르거든요. 성능은 캐시를 얼마나 잘 활용하는지, 상수가 얼마나 큰지, 실제 입력이 얼마나 큰지에 따라 크게 달라져요. 그래서 복잡도 분석과 벤치마크를 한 세트로 생각하는 습관이 중요해요.
배차, 스케줄링, 배치 최적화처럼 NP-난해한 문제를 만나도 너무 겁먹을 필요는 없어요. 최악의 경우가 어렵다는 것과 내가 가진 실제 데이터가 어렵다는 건 다른 얘기거든요. 실제로 요즘 SAT 솔버는 변수가 수백만 개인 산업 현장의 문제도 꽤 잘 풀어내요.
마무리
빅오는 지도일 뿐이고, 실제 지형은 직접 걸어봐야 알 수 있어요. 이론상 더 좋은 알고리즘이 실제로는 더 느렸던 경험이 있으신가요? 있다면 이유는 뭐였나요?
🔗 출처: Hacker News