빅오는 질문 하나야: 일이 얼마나 빨리 커져?

"빅오는 무슨 비밀 결사 이름처럼 들려. 사실은 컴퓨터 과학에서 제일 안 무서운 개념이야. 데이터를 두 배로 하면 일은 어떻게 되지?"

무서운 거 벗겨내기

사람들이 빅오를 비밀 악수처럼 다뤄. 아니야. 'O'는 "~의 차수로"라는 뜻이고, 규모에서 안 중요한 디테일은 무시한 채 성장의 모양만 대충 그리겠다는 선언이야. 앞으로 만날 모든 빅오가 질문 하나에 답해. 입력이 두 배가 되면 일의 양은 어떻게 되나?

질문은 그 하나로 끝이야. 제일 흔한 답 세 개면 거의 다 설명돼.

O(1) — 상수. 데이터가 두 배여도 일은 그대로. dict 에서 단어 하나 찾는 건 항목이 10개든 천만 개든 신경 안 써.
O(n) — 선형. 데이터가 두 배면 일도 두 배. 리스트의 모든 항목을 한 번씩 읽는 경우야.
O(n²) — 제곱. 데이터가 두 배면 일은 네 배. 모든 항목을 다른 모든 항목과 비교하는 경우고.

두 배 테스트

복잡도를 추상 대신 물리적으로 만드는 요령이 있어. 아무 함수나 골라서 n개에 돌리고, 2n개에 돌리고, 일이 어떻게 되는지 봐.

일이 그대로면 O(1).
두 배가 되면 O(n).
네 배가 되면 O(n²).
딱 고정된 만큼만, 한 단계쯤 늘었으면 O(log n). 곧 만날 마법 같은 녀석이야.

이 테스트는 코드를 읽으면서 머릿속으로 돌려도 되고, 아래 코드처럼 카운터를 달아 진짜로 돌려도 돼. 두 배가 반사신경이 되면 복잡도가 페이지에서 바로 읽혀.

빅오는 딱 하나에 답해. 입력이 커지면 일은 그에 따라 어떻게 커지나? 상수, 선형, 제곱. 이 세 가지 성장 모양이면 어휘는 거의 다 갖춘 셈이야.

왜 쓰레기를 버리나

빅오는 일부러 상수와 작은 항을 무시해. 2n + 7단계를 밟는 알고리즘도 여전히 O(n)이야. n이 백만이 되면 2와 7은 n 옆에서 보이지도 않거든. 대충 하는 게 아니라, 규모에서 코드의 생사를 가르는 단 하나의 지배적인 모양에 집중하는 거야. 그 모양을 반복문에서 바로 읽어내는 법은 바로 다음에 나와.

피파의 고백

아빠가 네 단어로 줄여주기 전까지 빅오는 날 겁줬어. "두 배 하고, 일을 봐." 그러자 그리스 문자처럼 생긴 표기가, 코드를 두 번 돌리면 몸으로 느낄 수 있는 것에 붙은 라벨일 뿐이 됐어. "오 오브 엔"을 주문처럼 외는 걸 그만두고 실제로 두 배가 되는 걸 보기 시작했지. 표기는 목적지고, 두 배 테스트는 거기까지 가는 길이야.

Code

두 배 테스트를 숫자로·python

# 두 배 테스트를 진짜로. n 에 돌리고, 2n 에 돌리고, 일을 봐.

def work_constant(items):      # O(1): 첫 항목만 슬쩍
    return 1                    # 항목이 몇 개든 한 단계

def work_linear(items):        # O(n): 모든 항목 한 번씩 건드림
    return len(items)           # n 단계

def work_quadratic(items):     # O(n^2): 모든 쌍
    n = len(items)
    return n * n                 # n*n 단계

for n in (1_000, 2_000):       # n, 그다음 2n
    items = list(range(n))
    print(f"n={n:>5} | O(1)={work_constant(items):>2}  "
          f"O(n)={work_linear(items):>5}  O(n^2)={work_quadratic(items):>10}")

# n 두 배:  O(1) 은 1 그대로.  O(n) 은 두 배.  O(n^2) 은 4배.
# 그 비율이 곧 복잡도야. 스톱워치 필요 없어.

Exercise

코드 없이 빅오를 말해봐. (1) 정렬 안 된 수 n개에서 최댓값 찾기, (2) 첫 원소가 마지막 원소와 같은지 확인, (3) 방에 있는 n명이 서로 전부 악수하기. 그다음 n이 두 배가 되면 각각 일이 어떻게 되는지 예측해.

Hint

각각이 항목을 몇 개나 건드리는지 세봐. (2)는 n과 상관없이 두 개만 건드려. (3)은 모든 쌍이니까 제곱짜리야.

무서운 거 벗겨내기

두 배 테스트

왜 쓰레기를 버리나

피파의 고백

Code

External links

Exercise

Progress

댓글 0