어레이의 요소에 액세스하는 데 일정한 시간이 걸리는 이유는 무엇입니까?

어레이의 요소에 액세스하는 데 일정한 시간이 걸리는 이유는 무엇입니까?

다음과 같은 어레이가 있다고 가정합니다.

int a[]={4,5,7,10,2,3,6}

예를 들어 요소에 액세스 할 때a[3]무대 뒤에서 실제로 무슨 일이 일어나나요?왜 많은 알고리즘북(Cormen북 등)은 일정한 시간이 걸린다고 말하는가?

(저는 저급 프로그래밍의 초보자이기 때문에 여러분들에게 더 배우고 싶습니다.)

어레이는 사실상 메모리 위치(포인터)에 의해 인식됩니다.액세스a[3]location_of_a+3*sizeof(int)이기 때문에 일정 시간 내에 찾을 수 있습니다.

C에서는 이것을 직접 볼 수 있습니다.기억하세요.a[3]와 같다*(a+3)동작에 관해서는 조금 더 명확합니다(포인터 「3개의 아이템」을 참조).

지수 0 ~ 9를 가진 10개의 정수 변수 배열은 메모리 주소 2000, 2004, 2008, … 2036에 10개의 워드로 저장될 수 있습니다. 따라서 지수 i를 가진 요소는 주소 2000 + 4 × i를 가집니다. 이 두 가지 연산은 일정한 시간이 걸리기 때문에 이 과정은 하나의 곱셈과 하나의 덧셈이 필요합니다.따라서 접속은 일정 시간 내에 실행할 수 있습니다.

즉, "선형 시간 내에 어떤 구조에 액세스할 수 있습니까?"Linked List 구조에 선형 시간 내에 액세스합니다.입수 방법n이동해야 하는 요소n-1이전 요소.테이프 레코더나 VHS 카세트처럼 테이프/VHS의 끝부분까지 가는 데 오랜 시간이 걸렸습니다.-)

어레이는 하드 디스크와 비슷합니다.모든 포인트에 "일정" 시간 내에 액세스 할 수 있습니다:-)

이것이 컴퓨터의 RAM을 RAM: Random Access Memory라고 부르는 이유입니다.주소를 알고 있는 경우는, 그 장소 앞에 있는 모든 메모리를 통과하지 않고, 어느 장소에도 액세스 할 수 있습니다.

HD 액세스는 일정한 시간이 아니라고 하는 사람도 있었습니다(액세스란 "헤드를 배치하고 HD의 한 섹터를 읽는 시간"을 의미합니다).나는 그것에 대해 확신하지 못한다고 말해야겠어요.구글을 검색해봤지만 그것에 대해 말하는 사람을 찾지 못했다.아직 랜덤으로 접속되어 있기 때문에 시간이 선형적이지 않다는 것은 알고 있습니다.결국, HD 액세스가 충분히 일정하지 않다고 생각되는 경우(그렇다면, 무엇이 일정할까요?)캐시, 프리페치, 데이터 로컬리티 및 컴파일러 최적화를 고려하여 RAM에 액세스 할 수 있습니다.) "어레이는 USB 디스크 스틱에 가깝습니다.모든 포인트는 "일정" 시간 내에 액세스 할 수 있습니다:-)

어레이는 순차적으로 메모리에 저장되기 때문입니다.실제로 어레이[3]에 액세스 할 때는, 컴퓨터에 「어레이의 선두의 메모리 주소를 취득해, 거기에 3을 더하고, 그 스폿에 액세스 합니다」라고 지시합니다.추가에 시간이 오래 걸리기 때문에 어레이 액세스에도 시간이 걸립니다.

액세스 할 필요가 있는 메모리의 위치를 알고 있는 경우는, 이 액세스는 일정한 시간내에 행해집니다.어레이의 경우 메모리 위치는 베이스 포인터, 소자 인덱스 및 소자 크기를 사용하여 계산한다.여기에는 실행에 일정한 시간이 걸리는 곱셈 및 덧셈 연산이 포함됩니다.따라서 어레이 내부의 요소 액세스에는 일정한 시간이 걸립니다.

배열은 순차적입니다. 즉, 배열에서 다음 요소의 주소가 현재 요소의 주소 옆에 있음을 의미합니다.따라서 어레이의 5번째 요소를 가져오려면 어레이의 기본 주소를 5로 합산하여 5번째 요소의 주소를 계산합니다.이 다이렉트주소는, 그 주소의 요소를 취득하기 위해서 직접 사용됩니다.

여기서도 같은 질문을 할 수 있습니다.「컴퓨터가 계산된 주소를 직접 인식/접속하는 방법」이것이 컴퓨터 메모리(RAM)의 특성과 원리입니다.RAM이 일정한 시간에 주소에 액세스하는 방법에 관심이 있는 경우, 모든 컴퓨터 조직의 텍스트에서 주소를 찾거나 구글에서 검색할 수 있습니다.

'문제 시간'은 '문제 크기에 의존하지 않는 시간'을 의미합니다.'문제'의 경우 '문제 크기'는 용기 크기입니다.

어레이 요소에 액세스하려면 컨테이너 크기에 관계없이 기본적으로 동일한 시간(이는 단순화)이 소요됩니다.이는 고정된 일련의 단계를 사용하여 요소를 검색하기 때문입니다. 메모리 내 위치(이것도 단순화)가 계산되고 메모리 내 해당 위치의 값이 검색되기 때문입니다.

예를 들어 링크된 목록은 각 링크가 다음 링크의 위치를 나타내기 때문에 이 작업을 수행할 수 없습니다.요소를 찾으려면 앞의 요소를 모두 조사해야 합니다.평균적으로 컨테이너의 절반을 조사하기 때문에 컨테이너의 크기가 매우 중요합니다.

배열은 유사한 유형의 데이터 모음입니다.따라서 모든 요소가 동일한 양의 메모리를 사용합니다.따라서 어레이의 기본 주소와 보유하고 있는 데이터 유형을 알고 있으면 아래 공식에 따라 어레이[i] 요소를 일정 시간 내에 쉽게 가져올 수 있습니다.

int takes 4 bytes in a 32 bit system.
int array[10];
base address=4000;
location of 7th element:4000+7*4.
array[7]=array[4000+7*4];

따라서 ih 요소가 보유하고 있는 기본 주소와 데이터 유형을 알고 있으면 일정 시간 내에 ih 요소를 얻을 수 있습니다.어레이 데이터 구조에 대한 자세한 내용은 이 링크를 참조하십시오.

언급URL : https://stackoverflow.com/questions/7297916/why-does-accessing-an-element-in-an-array-take-constant-time