AI Agent Developer 황화인 blog

시간복잡도_기초

10 min read

시간복잡도 기초 (Big-O)

한마디 요약: “입력 크기가 커질 때 연산 횟수가 얼마나 빨리 증가하느냐”를 나타내는 성장률 표기. 10개짜리에선 안 보이던 차이가 100만 개에서는 몇 초 vs 몇 시간의 차이로 벌어진다.

1. 시간복잡도가 뭔가

Time Complexity(시간복잡도, 입력 크기에 따른 연산 횟수 증가율): 알고리즘이 빠른지 느린지 판단하는 기준. 초 단위 실행 시간이 아니라 “입력 n이 2배로 늘면 연산이 몇 배로 늘어나나”를 보는 지표.

Big-O(빅오 표기법, 최악의 경우 성장률 표현): O(n), O(log n) 같은 표기. 여기서 n은 입력 크기(예: 리스트 원소 개수, 문서 길이, 토큰 수).

일상 비유: 택배 물류센터. 상자 100개 처리 시간은 직원이 빠르면 다 비슷하다. 그런데 10만 개 들어오면 “한 상자씩 처음부터 훑는 사람”과 “번호표 매겨서 바로 찾는 사람”의 차이가 몇 시간 단위로 벌어진다. 시간복잡도는 그 “훑는 방식”의 근본 차이를 측정한다.

포함 관계: 복잡도에는 시간복잡도와 Space Complexity(공간복잡도, 메모리 사용량 증가율) 가 있다. 둘 다 Big-O로 표기. 보통 시간이 더 중요해서 “복잡도” 하면 시간을 가리킨다.

2. 대표 복잡도 6종 나란히 비교

표기이름n=10n=1,000n=1,000,000대표 예시
O(1)상수(Constant)111해시맵 키 조회, 배열 인덱스 접근
O(log n)로그(Logarithmic)31020이진 탐색, 균형 트리 탐색
O(n)선형(Linear)101,0001,000,000리스트 전체 훑기, 문자열 훑기
O(n log n)선형로그3310,00020,000,000효율적인 정렬(merge sort, quicksort)
O(n²)이차(Quadratic)1001,000,0001,000,000,000,000이중 for문, 버블 정렬
O(2ⁿ)지수(Exponential)1,024엄청난 숫자사실상 영원부분집합 생성, 단순 피보나치 재귀

숫자로 보면 n²와 2ⁿ의 실전 위력이 느껴진다. 입력 100만 개일 때 O(n²)는 1조번 연산이 필요. 1초에 10억 번 하는 CPU로도 1000초, 약 17분.

3. 각 복잡도의 일상 비유

O(1): 전화번호부에서 “즐겨찾기” 버튼 누르기. 몇 명이 저장됐든 한 번에 끝.

O(log n): 1000쪽짜리 사전에서 단어 찾기. 가운데 펴고, 앞/뒤 결정, 또 가운데. 매번 절반씩 범위가 줄어듦. 1000쪽은 약 10번이면 끝(2¹⁰ = 1024).

O(n): 책 처음부터 끝까지 한 번 읽기. 쪽수가 2배면 시간도 2배.

O(n log n): 책 목차를 분류별로 다시 정렬. 전체를 훑되(n), 매 항목마다 올바른 위치 찾기(log n).

O(n²): 학생들이 서로 한 명씩 전부 악수하기. 10명이면 45번, 100명이면 4950번. 인원이 10배면 악수는 100배.

O(2ⁿ): 피자 토핑 조합 전부 시도. 토핑 3개면 8가지, 10개면 1024가지, 30개면 10억 가지. 토핑 하나 늘면 두 배.

4. Big-O 읽는 규칙 (단계 분해)

for i in range(n): for j in range(n): ... 같은 코드가 왜 O(n²)인지 계산하는 법.

1단계: 연산 횟수 식 세우기. 바깥 루프 n번, 안쪽 루프 n번 → n × n = n² 번.

2단계: 상수는 버리기. 3n² + 500n + 10000 이 있어도 n이 충분히 크면 n²이 지배. Big-O는 “얼마나 빨리 커지느냐”만 보므로 O(n²)로 쓴다.

3단계: 가장 큰 항만 남기기. n² + n 에서 n은 n²에 비하면 무시할 수 있음 → O(n²).

4단계: 계수 1로. 5n 도 O(n), 0.001n 도 O(n). 계수는 하드웨어나 언어에 따라 달라지므로 성장률만 본다.

5. Python에서 직접 확인

import time
 
def measure(func, n):
    start = time.perf_counter()
    func(n)
    return time.perf_counter() - start
 
# O(1): 리스트 인덱스 접근
def const_time(n):
    arr = list(range(n))
    return arr[n // 2]  # 크기에 상관없이 한 번
 
# O(n): 전체 합
def linear_time(n):
    return sum(range(n))
 
# O(n²): 이중 루프
def quadratic_time(n):
    total = 0
    for i in range(n):
        for j in range(n):
            total += 1
    return total
 
for n in [1000, 10000, 100000]:
    print(f"n={n}")
    print(f"  O(1)  : {measure(const_time, n)*1000:.3f} ms")
    print(f"  O(n)  : {measure(linear_time, n)*1000:.3f} ms")
    if n <= 10000:  # n=100000은 n²면 너무 오래
        print(f"  O(n²) : {measure(quadratic_time, n)*1000:.3f} ms")

돌려보면 n이 10배 될 때:

  • O(1): 시간 거의 그대로
  • O(n): 약 10배
  • O(n²): 약 100배

이 감각을 체득하는 게 시간복잡도 학습의 전부다.

6. 자료구조별 핵심 연산 복잡도

연산List해시맵 (dict)큐 (deque)균형 트리
접근(index/key)O(1)O(1) 평균O(n)O(log n)
탐색(값 찾기)O(n)O(1) 평균O(n)O(log n)
끝에 삽입O(1)O(1) 평균O(1)O(log n)
앞에 삽입O(n)N/AO(1)O(log n)
삭제(위치)O(n)O(1) 평균O(1) (양끝)O(log n)

핵심 포인트:

  • 값으로 찾을 일이 많다 → 해시맵 (O(1) 평균)
  • 순서대로 처리 → 큐 (양끝 O(1))
  • 정렬된 순회 + 빠른 탐색 → 트리 (O(log n))

7. AI Agent 개발에서 왜 중요한가

LLM 입력 크기 n = 토큰 수. 토큰이 많을수록 모든 처리가 느려지고 돈도 더 든다.

Context Window 활용: Anthropic Claude의 200K·1M 토큰 창에 문서를 몽땅 넣으면 검색은 필요 없지만 Attention 연산이 대략 O(n²) 에 가까워짐(토큰끼리 서로 참조). 토큰 2배 → 추론 시간 약 4배, 비용도 4배.

RAG(Retrieval-Augmented Generation): 벡터 DB에서 유사 문서 k개만 뽑아 넣는 이유. 전체가 아니라 k개만 보면 n이 확 줄어 O(n²)의 지옥에서 탈출.

벡터 검색: 단순하게 전 벡터와 코사인 유사도 비교는 O(n). 실전은 ANN(Approximate Nearest Neighbor, 근사 최근접 탐색) 알고리즘(HNSW, IVF)으로 O(log n)에 가깝게 내려침. FAISS, Pinecone, Qdrant가 다 이걸 쓴다.

캐싱 전략 선택: 프롬프트 캐시는 해시맵의 O(1) 덕분에 즉시 히트 판정이 가능. 캐시 키를 잘못 설계해서 매번 다른 키가 되면 히트율 0.

Agent 툴 선택 분기: 툴이 많아질수록 “어떤 툴을 쓸까?” 결정에 드는 토큰·시간이 선형 증가. 툴 수가 n이면 프롬프트 안의 툴 설명 길이도 대략 n배.

8. 실전에서 기억할 것

상수를 완전히 무시하진 말자: Big-O는 점근적(입력이 매우 클 때) 분석. n이 작으면 상수가 큰 O(log n)보다 상수가 작은 O(n)이 더 빠를 수 있다. 실제로는 프로파일링해서 확인.

평균 vs 최악: 해시맵은 평균 O(1)이지만 충돌이 극단적이면 최악 O(n). 신뢰성이 중요한 곳(실시간 시스템, 금융)에서는 최악 기준으로 설계.

공간 vs 시간 트레이드오프: 캐싱은 공간(메모리)을 써서 시간을 줄이는 전형적 거래. “메모이제이션(memoization, 계산한 결과를 해시맵에 저장해 재활용)“이 대표 기법.

9. 관련 문서

  • 해시맵: O(1) 조회의 대표 주자
  • 큐: O(1) 삽입·삭제의 대표 주자
  • 트리: O(log n) 탐색의 대표 주자
  • 직렬화_JSON_YAML: 데이터 크기가 커질수록 파싱 시간이 O(n)으로 쌓임

Graph View

Backlinks