Page 25 -

그렇다면 컴퓨터가 배열에서 선형 검색을 수행하는 데 필요한 최대 단계 수는 얼마일까?

("elderberries"처럼) 찾고 있는 값이 배열의 마지막 셀에 있다면 컴퓨터는 이 값을 발견할 때까
지 배열의 모든 셀을 검색해야 한다. 또한, 찾고 있는 값이 배열의 어떤 셀에도 없으면 마찬가지로
모든 셀을 검색해야 비로소 배열에 값이 없다고 확신할 수 있다.

따라서 5개의 셀로 이뤄진 배열에서 선형 검색에 걸리는 최대 단계 수는 5다. 500개의 셀로 이뤄
진 배열이라면 선형 검색에 걸리는 최대 단계 수는 500이다.

달리 표현하면 N개의 셀로 이뤄진 배열은 선형 검색에 최대 N개의 단계가 필요하다고 말할 수 있
다. 이때 N은 어떤 수든 넣을 수 있는 단순한 변수다.

어쨌든 검색은 읽기보다 분명히 덜 효율적이다. 읽기는 배열이 얼마나 크든 항상 한 단계만 걸리
지만 검색에는 많은 단계가 걸릴 수 있다.

다음으로는 삽입 연산을 알아보자.

1.6 삽입 DATA STRUCTURES AND ALGORITHMS

배열에 새 데이터를 삽입하는 연산은 배열의 어디에 데이터를 삽입하는가에 따라 효율성이 다르다.
쇼핑 목록의 맨 끝에 "figs"를 추가해 보자. 이 삽입에는 딱 한 단계만 필요하다.

이는 컴퓨터의 또 다른 특징, 즉 배열을 할당할 때 항상 배열의 크기를 기록한다는 특징에 기인
한다.

앞서 컴퓨터는 배열이 시작되는 메모리 주소를 안다고 했으니 두 특징을 맞물려 생각해 보면 배열
마지막 항목의 메모리 주소를 계산하기 아주 쉽다. 배열이 메모리 주소 1010에서 시작하고 크기

가 5면 마지막 메모리 주소가 1014다. 따라서 그 뒤에 항목을 삽입하면 다음 메모리 주소인 1015
에 항목을 추가한다는 뜻이다.

이제 컴퓨터는 새 값을 삽입할 메모리 주소를 계산할 수 있고, 이는 한 단계면 된다.

038