어떻게 빠르기를 재는 자

초 대신 횟수

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

입력 크기를 고르면 방법마다 일하는 횟수가 나온다. (하나씩 = n번 · 반씩 = 훨씬 적은 횟수)

칸이 적을 때는 둘이 비슷해 보인다.
8칸이면 하나씩은 8번, 반씩은 3번이라 차이가 별로 없다.
그럼 칸을 확 늘리면 어떻게 될까요?

키우면 생기는 일

여기서 진짜 차이가 보인다.
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²은 위로 폭발. 큰 항만 보면 돼요.

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