Page 12 -

왜 그럴까?
누구도 어떤 연산이, 예컨대 정확히 5초가 걸린다고 단정할 수 없다. 같은 연
산도 어떤 컴퓨터에서는 5초가 걸리고, 구형 하드웨어에서는 더 오래 걸릴

수 있으며, 미래의 슈퍼컴퓨터에서는 훨씬 빠를 수 있다. 시간은 연산을 실행
하는 하드웨어에 따라 항상 바뀌므로 시간을 기준으로 속도를 측정하면 신뢰
할 수 없다.

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

측정하는 게 연산의 속도를 분석하는 핵심 비결이다.

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

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

1.2 읽기 data structures and algorithms

첫 번째로 살펴볼 연산인 읽기는 배열 내 특정 인덱스에 어떤 값이 들어 있는
지 찾아보는 것이다. 배열에서 읽기는 실제로 딱 한 단계다. 컴퓨터는 배열

내 특정 인덱스에 한 번에 접근해서 볼 수 있기 때문이다. 앞선 ["apples",
"bananas", "cucumbers", "dates", "elderberries"] 예제에서 인덱스 2를

1장 자료 구조가 중요한 까닭 023

algorith06.indd 23 2018-06-25 오전 10:32:02