시간 복잡도와 Big-O 읽기

데이터가 10배 늘면 10배 느려질까?

개발자가 작성한 데이터 처리 스크립트가 1만 건의 사용자 요청을 처리하는 데 1초 걸렸다고 가정해 봅니다. 이 서비스가 인기를 얻어 처리해야 할 데이터가 10만 건으로 10배 늘어난다면, 작업에 걸리는 시간은 정직하게 10초로 늘어날까요?

경험이 부족한 개발자는 흔히 하드웨어의 클럭 속도나 스톱워치로 잰 단순 소요 시간만을 떠올리며 작업 시간이 데이터 크기에 정비례할 것이라 짐작합니다. 하지만 동일한 10배의 데이터 증가라 하더라도 어떤 프로그램은 1초에서 1.05초로 거의 차이 없이 끝나지만, 어떤 프로그램은 10초가 아니라 100초, 심지어 1,000초가 넘도록 반환되지 않고 서버 CPU를 100% 태우며 멈춰 버립니다.

이러한 극적인 격차가 발생하는 근본적인 이유는 알고리즘마다 입력 크기 N이 커질 때 필요한 기본 연산(비교, 산술, 메모리 접근) 횟수가 늘어나는 속도가 완전히 다르기 때문입니다. 데이터가 10배 늘어났을 때 연산이 10번만 더 늘어나는 알고리즘이 있는 반면, 10배로 늘어나는 알고리즘, 100배로 폭증하는 알고리즘, 그리고 입력 크기와 무관하게 단 1회의 연산으로 작업을 끝내는 알고리즘이 공존합니다.

프로그램의 성능을 객관적으로 평가하려면 특정 컴퓨터의 CPU 속도나 메모리 대역폭, 운영체제의 백그라운드 작업 부하 같은 환경적 변수를 걷어내야 합니다. 오직 입력 규모의 변화에 따라 연산량이 증가하는 수학적 추세를 분석해야 하며, 이 척도를 시간 복잡도(Time Complexity)라고 부릅니다.

점근 분석과 Big-O가 가려내는 증가율의 본질

알고리즘의 실행 단계를 한 줄 한 줄 세어 보면 3N² + 50N + 1000처럼 여러 항이 섞인 복잡한 다항식이 나옵니다. 하지만 N이 100만이나 1,000만처럼 극단적으로 커지는 점근적(Asymptotic) 상황을 가정하면, 최고차항인 N²의 영향력이 전체 연산량의 99.99% 이상을 지배하게 됩니다. 이때 계수 3이나 하위 항 50N + 1000은 증가 곡선의 기울기와 형태에 유의미한 차이를 만들지 못합니다.

소프트웨어 공학에서는 이처럼 사소한 세부 사항을 털어내고 데이터 증가에 따른 성장률의 상한선만을 단순화하여 나타내는 빅오 표기법(Big-O Notation)을 표준 언어로 사용합니다. 최고차항의 계수를 1로 정규화하고 하위 항을 과감히 생략하여 O(N²)과 같이 표기합니다.

알고리즘의 동작 특성은 입력 데이터의 초기 정렬 상태나 배치에 따라 달라지기도 합니다. 운 좋게 찾으려는 값이 배열의 맨 첫머리에 위치하는 최선의 경우(Best-case)나 무작위 표본의 평균적인 경우(Average-case)도 계산할 수 있습니다. 하지만 대규모 트래픽을 감당하는 시스템에서는 최악의 조건에서도 서버가 멈추거나 타임아웃을 내지 않도록 안전망을 설계해야 하므로, 가장 가혹한 입력 상태를 가정한 최악의 경우(Worst-case)를 기준으로 복잡도를 판정합니다.

[참고] 공간 복잡도와의 교환

시간 복잡도를 획기적으로 낮추기 위해 색인 트리나 해시 테이블 같은 추가 자료구조를 메모리에 보관하는 기법이 흔히 쓰입니다. 실행 속도를 얻는 대가로 메모리 공간을 더 소모하는 공간 복잡도(Space Complexity) 사이의 절충이 일어납니다.

데이터 규모에 따른 연산 증가 곡선

실무에서 자주 마주치는 복잡도 계층은 크게 다섯 단계로 나뉩니다. 데이터 규모 N이 가로축을 따라 오른쪽으로 전개될 때, 세로축의 연산 횟수가 위쪽으로 솟구치는 가파른 차이를 좌표 그래프와 우측 특성 카드로 대조해 살펴봅니다.

그림: 입력 크기 N의 증가에 따른 주요 시간 복잡도 곡선과 특성

좌표축의 변화율을 관찰하면 각 복잡도 등급이 대규모 데이터 환경에서 어떤 확장성을 발휘하는지 명확히 드러납니다.

• O(1) (상수 시간): 데이터 크기와 무관하게 연산 횟수가 고정됩니다. 해시 테이블 키 조회나 배열 인덱스 직접 접근이 해당하며, 규모 확장에 가장 이상적인 형태입니다.
• O(log N) (로그 시간): 밑이 2인 로그를 기준으로 데이터가 2배 뛸 때 연산은 1회 늘어납니다. 100만 건의 데이터라도 약 20번의 비교만으로 원하는 대상을 찾는 이진 탐색이 대표적입니다.
• O(N) (선형 시간): 연산 횟수가 데이터 개수에 1:1로 비례합니다. 정렬되지 않은 목록 전체를 처음부터 끝까지 훑는 단순 탐색이 이에 속합니다.
• O(N log N) (로그 선형 시간): 선형 순회와 분할 정복이 결합된 형태로, 병합 정렬이나 힙 정렬 등 비교 기반 정렬 알고리즘이 도달할 수 있는 수학적 최선입니다.
• O(N²) (이차 시간): 중첩 루프를 돌며 모든 원소 쌍을 일일이 맞대어 비교하는 단순 전수 조사가 해당하며, 대규모 서비스에서 치명적인 장애를 유발하는 주범입니다.

Python timeit으로 체감하는 O(1)과 O(N)

두 복잡도 사이의 차이가 실질적인 지연 시간으로 어떻게 나타나는지 Python 내장 timeit 모듈로 직접 계측해 봅니다. 10만 개의 정수가 순서대로 들어 있는 리스트와 집합을 준비하고, 컬렉션에 절대 존재하지 않는 값 -1의 포함 여부를 1,000회 연속 검사합니다. 리스트는 끝까지 모든 원소를 비교해야 하는 최악의 상황을 맞닥뜨리며, 집합은 해시 함수를 통해 즉시 부재를 판단합니다.

import timeit
 
data_size = 100_000
test_list = list(range(data_size))
test_set = set(test_list)
missing_target = -1
 
    # 리스트 포함 검사: O(N)
list_duration = timeit.timeit(
    lambda: missing_target in test_list,
    number=1_000
)
 
    # 집합 포함 검사: 평균 O(1)
set_duration = timeit.timeit(
    lambda: missing_target in test_set,
    number=1_000
)
 
print(f"리스트 1,000회 포함 검사: {list_duration:.6f}초")
print(f"집합 1,000회 포함 검사: {set_duration:.6f}초")
print(f"속도 비율: 리스트가 집합보다 약 {list_duration / set_duration:.1f}배 지연")

위 측정 코드를 실행하면 다음과 같은 형태의 수치가 콘솔에 집계됩니다.

예시 출력:
리스트 1,000회 포함 검사: 0.942180초
집합 1,000회 포함 검사: 0.000048초
속도 비율: 리스트가 집합보다 약 19628.8배 지연

측정 환경의 CPU 아키텍처와 운영체제 스케줄러에 따라 세부 숫자는 달라질 수 있으나, 주목해야 할 본질은 1만 배에서 2만 배에 이르는 극단적인 상대적 속도 격차입니다. 리스트는 10만 개의 원소를 매 호출마다 10만 번씩 총 1억 번 비교해야 하지만, 해시 버킷을 사용하는 집합은 단 한 번의 해시 계산과 슬롯 확인으로 탐색을 종결하기 때문입니다.

만약 데이터 크기를 10만 건에서 1,000만 건으로 100배 더 늘린다면, 리스트의 1,000회 검사 시간은 1분 30초를 훌쩍 넘어가지만 집합은 여전히 0.00005초 내외를 유지합니다. 복잡도의 등급이 다르면 하드웨어 증설로는 결코 메울 수 없는 격차가 벌어집니다.

중첩 루프의 함정과 실무 최적화

실무 코드에서 가장 흔하게 발생하는 성능 장애는 두 개의 목록을 대조하여 공통 원소를 추출하거나 중복을 제거할 때 무심코 작성하는 중첩 루프 패턴입니다.

    # 비효율적인 O(N × M) 교집합 추출
registered_users = ["user_1", "user_2", ...] # 5만 명
event_participants = ["user_3", "user_99", ...] # 5만 명
 
winner_list = []
for participant in event_participants:
    if participant in registered_users: # 리스트 탐색: O(N)
        winner_list.append(participant)

위 코드는 겉보기에는 직관적이지만, 바깥쪽 루프가 5만 번 도는 동안 안쪽의 리스트 in 연산도 매번 최대 5만 번의 비교를 수행하므로 전체 비교 횟수는 50,000 × 50,000 = 25억 회에 달합니다. 아무리 최신 서버라도 단일 스레드에서 25억 번의 문자열 비교는 수십 초 이상의 멈춤을 초래합니다.

이 문제를 해결하는 열쇠는 기준 대상을 해시 기반 집합으로 변환하는 것입니다. O(N)의 시간으로 registered_users를 집합으로 한 번만 변환해 두면, 루프 내부의 검사는 평균 O(1)로 줄어들어 전체 복잡도가 O(N + M)의 선형 시간으로 단축됩니다. 25억 번의 비교가 단 10만 번의 연산으로 줄어들며, 실행 시간은 30초에서 0.02초로 즉시 단축됩니다. 복잡도 분석은 이처럼 코드 리팩터링의 정확한 타깃을 짚어 줍니다.

대규모 벡터 검색과 근사 알고리즘의 절충

시간 복잡도의 직관은 최신 AI 시스템 파이프라인을 운영할 때 더욱 강력한 무기가 됩니다. 거대 언어 모델에 방대한 외부 지식을 실시간 공급하는 RAG 파이프라인에서는 사용자의 질문 문장을 고차원 임베딩 벡터로 변환한 뒤, 지식베이스에 저장된 수많은 문서 청크 벡터들과 유사도를 계산해야 합니다.

문서 청크가 100만 개 쌓여 있을 때 이를 단순 전수 조사로 하나씩 내적(Dot product) 계산하여 가장 유사한 상위 K개를 추려낸다면, 검색 복잡도는 O(N × D)가 됩니다(N은 문서 청크 수, D는 보통 1,536차원에 달하는 임베딩 차원). 질문 하나가 들어올 때마다 15억 번의 부동소수점 곱셈과 덧셈을 수행해야 하므로, GPU 가속기를 동원하더라도 수백 밀리초에서 수 초의 지연이 발생해 실시간 대화형 에이전트의 반응성이 무너집니다.

프로덕션 벡터 데이터베이스는 이 병목을 정면 돌파하기 위해 근사 최근접 탐색(Approximate Nearest Neighbor; ANN) 기법을 채택합니다. HNSW(Hierarchical Navigable Small World)와 같은 그래프 기반 색인은 다층 고속도로망처럼 연결된 벡터 그래프를 계층적으로 건너뛰며 탐색 공간을 좁힙니다. 수학적으로 100% 완벽한 최근접 벡터 대신 99% 이상 유사한 근사 결과를 허용하는 대신, 검색 복잡도를 O(N)의 선형 탐색에서 O(log N)의 로그 수준으로 끌어내립니다. 100만 건의 문서 속에서도 20~30회의 도약만으로 관련 문맥을 밀리초 이내에 찾아내는 비결이 바로 이 복잡도 다운그레이드 전략에 있습니다.

데이터의 규모가 커질수록 알고리즘의 시간 복잡도는 시스템의 생존을 결정합니다. 병목이 어디에서 발생하는지 점근적으로 분석할 수 있는 엔지니어만이 자원 낭비 없이 안정적인 대규모 인프라를 설계할 수 있습니다.

참고 문서

• Python 공식 문서 — timeit 모듈
• MIT OpenCourseWare — Introduction to Algorithms (Spring 2020)
• RFC 9293 — Transmission Control Protocol (TCP)
• Pinecone Learning Center — Hierarchical Navigable Small World (HNSW)