같은 코드가 어느 순간 갑자기 멈춘다
개발 단계에서 잘 작동하던 기능이 사용자 수가 일정 규모를 넘는 순간 갑자기 응답 속도가 무너지는 경험은 거의 모든 서비스가 겪는다. 원인은 대부분 알고리즘 복잡도다. 입력 크기가 100일 때 0.01초 걸리던 함수가 입력 크기 10,000에서 10초 가까이 걸린다면 그 함수의 시간 복잡도는 O(n²)일 가능성이 높다. MIT 6.006 알고리즘 입문 강의는 첫 강의의 절반을 이 점근적 분석 개념에 할애한다. 코드의 줄 수가 아니라 입력 크기에 따른 실행 시간의 성장률이 진짜 비용이라는 점을 가장 먼저 짚고 가는 셈이다.
이 차이는 코드 한 줄을 보고서는 보이지 않는다. 중첩된 반복문 두 개로 작성된 코드는 입력이 작을 때는 단일 반복문 코드와 거의 같은 속도로 작동한다. 그러나 입력이 100배 커지면 O(n) 알고리즘은 100배 느려지는 반면 O(n²) 알고리즘은 만 배 느려진다. 같은 100배 증가가 두 알고리즘에 100배의 차이를 만든다.
입력이 작을 때는 차이가 안 보인다
이 문제가 까다로운 이유는 작은 데이터로 테스트할 때 두 알고리즘이 거의 똑같이 보인다는 데 있다. 사용자 100명 환경에서는 두 코드 모두 밀리초 단위로 끝난다. QA 단계, 베타 단계까지 통과한 코드가 실제 운영에서 무너지는 일은 이 구조에서 자주 발생한다. 입력 크기와 실행 시간의 관계는 선형이 아니라 곡선이며, 곡선의 모양이 알고리즘의 복잡도다.
해시 테이블이 자주 등장하는 패턴은 메모리를 더 써서 시간을 줄이는 절충안이다. 키 검색을 O(n)에서 O(1)에 가까운 평균 시간으로 만들기 위해 추가 메모리를 소비한다. 다만 해시 함수 설계가 부실하면 충돌이 자주 발생하면서 O(1)이 깨진다. 이 부분은 생일 문제와 해시 충돌의 수학에서 별도로 다룬 적이 있다.
표기법이 알려주는 것과 가리는 것
빅오 표기법은 입력 크기 n이 충분히 커졌을 때의 점근적 성장률만 표현한다. 상수 항과 낮은 차수의 항은 무시된다. 그래서 같은 O(n) 알고리즘이라도 실제로는 두 배에서 열 배까지 속도 차이가 날 수 있다. 작은 n에서는 오히려 이론적으로 더 느린 알고리즘이 더 빠른 경우도 있다. 표기법은 큰 그림을 보여주지만 작은 그림은 가린다.
이 표기법은 1894년 독일 수학자 폴 바흐만(Paul Bachmann)이 정수론 교과서에서 처음 도입했고, 컴퓨터과학에서는 도널드 커누스(Donald Knuth)가 1976년 SIGACT 뉴스레터에 게재한 짧은 논문 “Big Omicron and Big Omega and Big Theta”를 통해 표준 용법으로 정착되었다. 수학에서 시작된 점근 표기법이 시스템 설계의 공용 언어가 되기까지는 80년이 걸렸다.
로그 시간이 산업 단위에서 만든 격차
O(log n) 알고리즘과 O(n) 알고리즘의 차이는 산업 단위에서 더 크게 드러난다. 데이터베이스의 B-Tree 인덱스가 검색 시간을 O(log n)으로 유지하지 않았다면 현대의 대규모 데이터베이스는 작동하지 않았을 것이다. 10억 건 데이터에서 인덱스 없는 검색은 평균 5억 번의 비교를 요구하지만 B-Tree 검색은 30회 안팎으로 끝난다.
마찬가지로 정렬 알고리즘에서 O(n²) 버블 정렬이 O(n log n) 퀵 정렬로 대체된 이후 데이터 처리량이 단순히 빨라진 게 아니라 다룰 수 있는 데이터의 규모 자체가 바뀌었다. 알고리즘 복잡도의 개선은 같은 일을 더 빨리 하게 만드는 게 아니라 이전에는 시도조차 불가능했던 작업을 가능하게 만든다.
최악의 경우가 결정적이 되는 분야
일반 서비스에서는 평균 복잡도로 충분하지만 보안, 의료, 항공 같은 분야에서는 최악의 경우 복잡도가 결정적이다. 평소에는 빠르게 작동하지만 특정 입력에 대해 O(2ⁿ) 시간이 걸리는 알고리즘은 공격자에게는 정확히 그 입력을 만들어 서비스 거부 공격을 시도할 동기를 준다. 정규표현식 일부 패턴이 만드는 catastrophic backtracking이 대표 사례인데, OWASP의 ReDoS 공격 분석은 잘못 설계된 정규식 한 줄이 서버 전체를 마비시키는 메커니즘을 사례별로 정리한다.
평균, 최악, 분할 상환을 함께 보는 이유
이 때문에 시스템 설계 단계에서 복잡도를 분석할 때는 평균, 최악, 분할 상환(amortized) 세 가지를 함께 보는 게 표준이다. 동적 배열의 append 연산이 대표적이다. 대부분의 호출은 O(1)이지만 배열이 가득 차서 크기를 두 배로 늘려야 할 때는 O(n)이 걸린다. 전체 n번의 호출을 합산해 평균을 내면 다시 O(1)에 수렴한다. 이 분할 상환 분석을 빼고 최악만 보면 동적 배열이 비효율적인 자료구조처럼 보이지만 실제로는 그렇지 않다.
알고리즘이 빠른지 느린지를 묻는 단순한 질문 뒤에 입력 조건, 메모리 제약, 운영 환경이라는 여러 축이 함께 들어 있다. 복잡도 분석은 한 가지 숫자로 답을 내는 도구가 아니라 어떤 상황에서 어떤 비용이 지배적인지를 분해하는 언어다.