배열에 데이터를 저장한 후 데이터에 접근하는 연산을 생각해 봅시다. 배열에서는 인덱싱(indexing)을 이용하여 데이터에 접근합니다. 알다시피 인덱스는 0부터 시작하지요. 배열의 요소가 메모리에 선형적으로 존재하기 때문에 인덱싱은 다음과 같은 간단한 수식의 연산만으로도 쉽게 데이터에 접근할 수 있습니다.

데이터 주소 값 = 배열의 첫 주소 값 + (데이터 크기 * 인덱스)

이 수식은 한 번의 연산으로도 값에 접근할 수 있으므로 빅오는 O(1)입니다. 그림으로 이 수식을 이해해 봅시다(그림 3- 6).

▲ 그림 3-6 인덱싱

그림 3- 6을 보면 데이터 크기는 4바이트이므로 arr[3]에 접근하려면 그저 start+(4*3) 연산만 수행하면 됩니다. 이는 데이터 개수가 1만 개이든 2만 개이든 상관없이 딱 한 번만 연산하면 됩니다. 정말 놀랄 만한 성능이지요.