빠르기를 재는 자

횟수를 세요

초로 재면 헷갈려요.
빠른 컴퓨터에선
느린 방법도 빨라 보이죠.
그래서 초 대신
'몇 번 일하나'를 세요.
칸이 n개일 때
방법마다
일하는 횟수가 달라요.

입력 크기를 골라, 방법마다 일하는 횟수를 세 봐요. (하나씩 = n번 · 반씩 = 적은 횟수)

칸이 적을 땐
둘이 비슷해 보여요.
8칸이면
하나씩 8번,
반씩 3번.
별 차이 없죠.
근데 칸을 확 키우면
어떻게 될까요?

키우면 어떻게

여기서 진짜가 보여요.
n을 키워 보면
어떤 방법은
칸만큼 천천히 늘고,
어떤 방법은
칸이 두 배면
일이 네 배로 뛰어요.
n 곱하기 n,
그게 n²이에요.

n을 눌러 키워 보세요. n은 칸만큼 늘지만, n²은 칸이 커질수록 폭발하듯 늘어요.

n²이 무서운 건
칸이 클 때예요.
100칸이면
n은 100,
n²은 10000.
1000칸이면
n은 1000,
n²은 백만이에요.
작게 시작해도
금세 손쓸 수 없이 커져요.

곡선을 비교

세 가지 자라기를
나란히 두면
한눈에 보여요.
log n은
칸이 커져도
거의 안 올라가요.
n은 비스듬히 곧게,
n²은 위로 휘어
저 멀리 치솟아요.

곡선을 눌러 켜며 비교해요. 같은 n에서도 log n · n · n²의 높이가 완전히 달라요.

이제 알겠죠.
반씩 자르기가
왜 그리 빨랐는지.
반씩은 log n,
칸이 천 개라도
열 번이면 끝나요.
하나씩은 n,
천 개면 천 번.
자라는 모양이
승부를 가른 거예요.

큰 항만 남겨요

실제 횟수를 세보면
3n²+5n+9처럼
식이 지저분해요.
근데 n이 아주 커지면
n²이 다른 걸
다 압도해요.
그래서 작은 항은 지우고
가장 크게 자라는
n²만 남겨요.

작은 항을 눌러 하나씩 지워 봐요. 3n²+5n+9에서 n이 크면 n²만 남고, 그게 빅오(O)예요.

앞의 숫자도 지워요.
3n²이든 100n²이든,
자라는 모양은 똑같이 n²이니까요.
그래서 그냥
O(n²)이라고 적어요.
빅오는 '큰 칸에서
어떤 모양으로 자라나'를
한 줄로 적은 이름표예요.

여기까지 왔어요

정리하면 이래요.
빠르기는 초가 아니라
자라는 모양으로 재요.
칸 n이 커질 때
log n은 거의 안 늘고,
n은 칸만큼,
n²은 폭발해요.
식이 복잡해도
큰 항 하나만 보면 되고,
그 표시가 빅오예요.

세 가지를 눌러 한 줄로 정리해요. log n은 거의 평평, n은 비스듬히, n²은 위로 폭발. 큰 항만 보면 돼요.

이제 방법을 보면
초를 안 재도
빠른지 가늠할 수 있어요.
칸이 두 배일 때
일이 두 배면 괜찮고,
네 배로 뛰면 조심.
좋은 방법은
큰일 앞에서도
천천히 자라는 방법이에요.