그렇다면 연산의 속도를 어떻게 측정할까?

이 책에서 오직 한 가지만 배워야 한다면 바로 이 점을 기억하자. 연산이 얼마나 “빠른가”를 측정할 때는 순수하게 시간 관점에서 연산이 얼마나 빠른가가 아니라 얼마나 많은 단계가 필요한지를 논해야 한다.

2부터 100 사이의 짝수를 출력하는 예제에서 이미 한 번 알아봤다. 두 번째 버전의 함수가 첫 번째 버전보다 단계가 절반밖에 걸리지 않아 더 빨랐다.

왜 코드의 속도를 단계로 측정할까?

누구도 어떤 연산이, 예컨대 정확히 5초가 걸린다고 단정할 수 없기 때문이다. 같은 연산도 어떤 컴퓨터에서는 5초가 걸리고, 구형 하드웨어에서는 더 오래 걸릴 수 있다. 미래의 슈퍼컴퓨터에서는 훨씬 빠를 수도 있다. 시간은 연산을 실행하는 하드웨어에 따라 항상 바뀌므로 시간을 기준으로 속도를 측정하면 신뢰할 수 없다.

대신 연산의 속도를 측정할 때 얼마나 많은 계산 단계(step)가 필요한가를 따져볼 수 있다. 연산 A에 5단계가 필요하고 연산 B에 500단계가 필요하면, 모든 하드웨어에서 연산 A가 연산 B보다 항상 빠를 거라고 가정할 수 있다. 결국 단계 수 측정이 연산 속도를 분석하는 핵심 비결이다.

연산의 속도 측정은 연산의 시간 복잡도 측정으로도 알려져 있다. 이 책 전반에서 속도와 시간 복잡도, 효율성, 성능이라는 용어를 같은 의미로 사용하겠다. 네 용어 모두 주어진 연산에 걸리는 단계 수를 나타낸다.

이제 배열에 쓰이는 네 가지 연산으로 돌아가서 각각 얼마나 많은 단계가 필요한지 알아내 보자.