배열 요소에 접근하는데 O(1)의 시간이 걸리는 이유

배열은 선형 데이터 구조입니다.

배열은 메모리에 연속적으로 할당되므로 배열의 인덱스를 통해 값을 가져오는 것은 산술 연산입니다.

산술 연산은 O(1)로 수행됩니다.

배열에는 인덱스 0의 메모리 주소가 있습니다. 인덱스 번호와 한 요소의 크기(int일 경우 4바이트)를 기본 주소에 더하면 해당 인덱스 값의 주소를 얻을 수 있습니다.

i번째 인덱스 주소 = 0번째 인덱스 주소 + i x (한 요소의 크기)

 

예시

int[] arr = {1,2,3,4,5}

 

arr 배열에서 인덱스 0의 메모리 주소를 100이라고 가정했을 때 3번째 인덱스 주소를 얻을려면

100 + 3 * 4 = 112의 메모리 주소값을 얻습니다.