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

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

무서운 거 벗겨내기

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

그게 다야. 제일 흔한 답 세 개가 거의 전부를 말해줘:

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

두 배 테스트

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

일이 그대로? O(1).
일이 두 배? O(n).
일이 × 4? O(n²).
일이 딱 고정량만큼 (한 단계 더) 늘었어? O(log n) — 곧 만날 마법 같은 녀석이야.

이 테스트를 코드 읽으면서 머릿속으로 돌릴 수도 있고, 아래 스니펫처럼 카운터로 진짜 돌릴 수도 있어. 두 배가 반사신경이 되면, 복잡도를 페이지에서 바로 읽어내.

빅오는 정확히 질문 하나에 답해: 입력이 커지면, 일은 그에 따라 어떻게 커져? 상수, 선형, 제곱 — 그 성장의 모양이 어휘 전부야.

왜 쓰레기를 버리나

빅오는 일부러 상수랑 작은 항을 무시해. 2n + 7 단계를 하는 알고리즘도 여전히 O(n) 이야 — n 이 백만이 되면 2 랑 7 은 n 옆에서 안 보이거든. 대충 하는 게 아니라, 규모에서 코드가 살아남는지를 결정하는 유일한 것 — 지배적인 모양 — 에 집중하는 거야. (다음 lesson 이 그 모양을 반복문에서 바로 읽어내는 법을 보여줘.)

피파의 고백

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

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