19강 / 20강

시간 복잡도 — 데이터가 100배가 되면

빠르다·느리다를 말로 하지 않고 정확히 표현하는 법

지금까지 🐢와 ⚡ 로만 이야기했습니다. 이제 제대로 된 이름을 붙일 차례입니다.

Big-O 표기법은 "이 코드가 몇 초 걸리는가"가 아니라 "데이터가 늘어날 때 시간이 어떤 모양으로 늘어나는가"를 나타냅니다.

왜 초로 말하지 않을까요? 컴퓨터마다 다르니까요. 하지만 "데이터가 2배면 시간도 2배"라는 모양은 어떤 컴퓨터에서든 똑같습니다.

표기	이름	n=10	n=1,000	n=1,000,000	예
O(1)	상수	1	1	1	리스트 인덱스, 딕셔너리 조회
O(log n)	로그	3	10	20	이진 탐색, 균형 트리
O(n)	선형	10	1,000	1,000,000	리스트 전체 훑기
O(n log n)	선형로그	33	10,000	20,000,000	병합·퀵 정렬
O(n²)	제곱	100	1,000,000	1조	버블 정렬, 이중 반복문
O(2ⁿ)	지수	1,024	천문학적	불가능	재귀 피보나치, 하노이 탑

1초에 1억 번 계산하는 컴퓨터라면, n=100만일 때 O(n)은 0.01초, O(n²)은 약 3시간입니다. 같은 문제, 같은 컴퓨터인데요.

고등학생데이터가 100배가 되면

19강은 말로 하던 것을 정확히 표현하는 법입니다.

"빠르다" 대신 "자료가 늘면 어떻게 되나" 를 말한다

왜 "빠르다" 로는 부족한가

말	문제
"0.1초 걸린다"	컴퓨터마다 다르다
"충분히 빠르다"	자료가 늘면?
"O(n²) 이다"	어디서든 같은 뜻 ✔

기계가 아니라 알고리즘의 성질을 말한다

주요 복잡도

표기	n 이 100배 되면	예
O(1)	그대로	딕셔너리 조회
O(log n)	+7 정도	이진 탐색
O(n)	100배	전부 훑기
O(n log n)	약 700배	정렬
O(n²)	1만 배 ⚠	이중 반복문
O(2ⁿ)	말할 수 없음	모든 부분집합

O(n²) 아래는 대체로 괜찮고 그 위는 대체로 못 쓴다

비유 — 교통수단

거리	걷기	자동차	비행기
1km	15분	3분	말이 안 된다
1000km	10일	10시간	1시간

가까우면 차이가 없고 멀어질수록 갈린다

🎮 복잡도 실험실

데이터 개수를 늘려 가며 실제 걸리는 시간을 재고 그래프를 그립니다. 표의 숫자가 아니라 곡선의 모양을 보세요.

고등학생왜 상수와 낮은 항을 버리나

O 표기는 과감하게 버립니다.

실제	O 표기
3n² + 100n + 5000	O(n²)
0.5n	O(n)

n 이 커지면 가장 높은 항이 전부를 지배한다

숫자로 보면

n	3n²	100n	비중
10	300	1,000	100n 이 크다
100	30,000	10,000	비슷
10,000	3억	100만	n² 이 99.7%

커지면 나머지는 없는 것과 같다

비유 — 여행 시간

서울에서 부산까지 —

구간	시간
집 → 역	20분 (고정)
기차	거리에 비례

부산이면 20분이 의미 있지만 지구 반대편이면 20분은 없는 셈이죠.

규모가 커지면 고정 비용은 사라진다

그런데 조심할 것

실무에서 n 이 작으면 상수가 중요합니다.

상황	어느 쪽이 빠른가
n = 10	단순한 O(n²) 이 이길 수 있다
n = 100만	O(n log n) 이 압도

그래서 Timsort 는 작은 조각에 삽입 정렬을 쓴다 (17강)

Big-O 를 읽는 세 가지 규칙

가장 큰 항만 남긴다 — n² + 100n + 5000 → O(n²)
n이 충분히 크면 n²이 나머지를 압도합니다.
상수배는 무시한다 — 3n 도 100n 도 O(n)
모양이 같으면 같은 등급입니다. 컴퓨터를 100배 빠른 걸로 바꾸는 것과 같은 효과니까요.
최악의 경우를 말한다 — 운 좋으면 첫 칸에서 찾더라도 O(n)

④번이 함정입니다. 중첩 반복문이라고 무조건 n²이 아니에요.

Python 브라우저에서 실행

# 코드를 보고 복잡도 읽는 연습
값들 = list(range(10))

# ① O(1) — 개수와 무관
print(값들[5])

# ② O(n) — 반복문 한 겹
합 = 0
for ㅇ in 값들:
    합 += ㅇ

# ③ O(n²) — 반복문 두 겹
짝 = 0
for ㄱ in 값들:
    for ㄴ in 값들:
        짝 += 1
print("짝 개수:", 짝, "= 10 × 10")

# ④ O(n) — 두 겹처럼 보이지만 아닙니다! 안쪽이 개수와 무관
셈 = 0
for ㄱ in 값들:
    for ㄴ in range(3):
        셈 += 1
print("셈:", 셈, "= 10 × 3 → 3n → O(n)")

# ⑤ O(log n) — 매번 절반
ㄴ, 걸음 = 1024, 0
while ㄴ > 1:
    ㄴ //= 2
    걸음 += 1
print("1024를 절반씩:", 걸음, "번 →  log₂(1024) = 10")

고등학생숨어 있는 복잡도를 조심하세요

note 의 이 경고가 실전에서 가장 중요합니다.

한 줄처럼 보이는 것이 O(n) 일 수 있다

숨은 O(n) 들

코드	실제
`x in 리스트`	O(n) ⚠
`리스트.insert(0, v)`	O(n) ⚠
`리스트.pop(0)`	O(n) ⚠
`문자열 +=`	O(n) ⚠
`x in 집합`	O(1) ✔

반복문 안에 이게 있으면 O(n²) 이 된다

가장 흔한 사고

for x in 자료:            # n 번
    if x in 본것:         # ⚠ 여기서 또 n 번
        continue
    본것.append(x)

겉보기엔 반복문 하나인데 O(n²) 이다

본것 = set() 으로 한 글자만 바꾸면 O(n) 이 됩니다.

문자열 이어 붙이기도 같은 함정

# 나쁜 코드
s = ""
for w in 단어들:
    s += w          # ⚠ 매번 전체를 복사

# 좋은 코드
s = "".join(단어들)  # ✔ O(n)

문자열은 못 바꾸는 자료라 매번 새로 만든다 (4강)

비유 — 계산기 안 보이는 버튼

"한 번 누르면 한 번 계산" 이라 생각했는데 어떤 버튼은 안에서 100번 계산한다면?

겉보기 줄 수와 실제 일의 양은 다르다

그래서 자료구조의 비용을 알아야 합니다. 이 강의 전체가 그걸 위한 거예요.

한 줄 고쳐 등급을 내리는 실전. 결과 개수는 같습니다.

Python 브라우저에서 실행

import time, random

큰목록 = [random.randint(0, 99999) for _ in range(20000)]
찾을것 = [random.randint(0, 99999) for _ in range(3000)]

# ① 리스트에서 in — 전체 O(n × m)
시작 = time.time()
개수1 = sum(1 for ㅇ in 찾을것 if ㅇ in 큰목록)
느림 = time.time() - 시작

# ② 집합으로 바꾸고 in — 전체 O(n + m)
큰집합 = set(큰목록)
시작 = time.time()
개수2 = sum(1 for ㅇ in 찾을것 if ㅇ in 큰집합)
빠름 = time.time() - 시작

print(f"리스트: {느림*1000:8.1f} ms  ({개수1}개 발견)")
print(f"집합  : {빠름*1000:8.1f} ms  ({개수2}개 발견)")
print(f"→ {느림/max(빠름,1e-9):.0f}배 차이. 바꾼 것은 한 줄뿐입니다.")

주요 연산의 복잡도 한눈에

자료구조	인덱스 접근	검색	맨 뒤 삽입	맨 앞 삽입	삭제
리스트	O(1)	O(n)	O(1)	O(n)	O(n)
연결 리스트	O(n)	O(n)	O(1)	O(1)	O(1)*
deque	O(n)	O(n)	O(1)	O(1)	O(1)*
딕셔너리 · 집합	—	O(1)	O(1)	—	O(1)
이진 탐색 트리(균형)	—	O(log n)	O(log n)	—	O(log n)
힙	—	O(n)	O(log n)	—	O(log n)**

* 위치를 이미 알고 있을 때 ** 최솟값 삭제

이 표를 외울 필요는 없습니다. "무엇이 빠른 그릇인가"를 찾아보는 습관이면 충분해요.

고등학생Big-O 가 전부는 아닙니다

note 의 이 경고가 균형을 잡아 줍니다.

O 표기는 큰 그림이지 실측이 아니다

O 가 놓치는 것들

요소	설명
상수	O(n) 인데 상수가 1000이면 느리다
캐시	연속 메모리가 몇 배 빠르다 (8강)
실제 n	n 이 10이면 뭘 써도 빠르다
최악 vs 평균	해시의 최악은 O(n) (13강)
메모리	빠른데 메모리가 없으면 못 쓴다

이론이 같아도 실제로 몇 배 차이가 난다

실제 사례 — 연결 리스트 vs 배열

	이론	실측
순회	둘 다 O(n)	배열이 수 배 빠르다

캐시 때문이다 — 8강에서 본 그 이야기

그럼 어떻게 하나

단계	도구
1. 차수를 본다	O 표기 — 큰 실수를 막는다
2. 실제로 잰다	time · 프로파일러
3. 실제 규모로	테스트 자료가 작으면 무의미

O 로 거르고, 측정으로 결정한다

비유 — 지도와 실제 도로

	알려 주는 것
지도 (O 표기)	거리 — 대략의 판단
실제 주행 (측정)	신호 · 정체 · 진짜 시간

지도로 경로를 고르고 실제로 가서 확인한다

지도 없이 가면 엉뚱한 방향으로 가고, 지도만 믿으면 정체를 모릅니다.

둘 다 필요하다 — 어느 하나로는 부족하다

🤔 확인 문제

3n² + 500n + 10000 의 시간 복잡도는?

🤔 확인 문제

for ㅇ in 목록: if ㅇ in 다른리스트: 의 전체 복잡도는? (둘 다 크기 n)

해설 바깥 반복이 n번, 안쪽 in 리스트가 매번 O(n)이므로 O(n²)입니다. 다른리스트를 집합으로 바꾸면 O(n)이 돼요.

🤔 확인 문제

1초에 1억 번 계산하는 컴퓨터로 n=1,000,000 을 처리할 때, 실용적으로 불가능한 것은?