Page 19 -

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

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

대신 연산의 속도를 측정할 때 얼마나 많은 계산 단계(step)가 필요한가를 따져볼 수 있다. 연산 A
에 5단계가 필요하고 연산 B에 500단계가 필요하면, 모든 하드웨어에서 연산 A가 연산 B보다 항

상 빠를 거라고 가정할 수 있다. 결국 단계 수 측정이 연산 속도를 분석하는 핵심 비결이다.
연산의 속도 측정은 연산의 시간 복잡도 측정으로도 알려져 있다. 이 책 전반에서 속도와 시간 복잡

도, 효율성, 성능이라는 용어를 같은 의미로 사용하겠다. 네 용어 모두 주어진 연산에 걸리는 단계
수를 나타낸다.

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

1.4 읽기 DATA STRUCTURES AND ALGORITHMS

첫 번째로 살펴볼 연산인 읽기는 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾아보는 것이다.

컴퓨터는 딱 한 단계로 배열에서 읽을 수 있다. 배열 내 특정 인덱스에 한 번에 접근해서 볼 수 있
기 때문이다. 앞선 ["apples", "bananas", "cucumbers", "dates", "elderberries"] 예제에서

인덱스 2를 찾아본다면 컴퓨터는 인덱스 2로 바로 가서 "cucumbers"라는 값이 있다고 알려줄 것
이다.

컴퓨터는 어떻게 단 한 단계로 배열의 인덱스를 찾아볼 수 있을까? 그 방법은 다음과 같다.
컴퓨터의 메모리는 셀로 구성된 거대한 컬렉션이라 할 수 있다. 다음 그림은 격자로 된 셀을 보여

준다. 어떤 셀은 비어 있고, 어떤 셀에는 데이터가 들어 있다.

032