почему доступ к элементу в массиве занимает постоянное время?

Question

Допустим, у меня есть массив как:

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

при доступе к элементу, напримеркак [3], что на самом деле происходит за сценой?Почему во многих книгах по алгоритмам (например, в книге Кормена ...) говорится, что это занимает постоянное время?

(я просто новичок в низкоуровневом программировании, поэтому я хотел бы узнать больше от вас, ребята)

Answer 1

Массив, по сути, известен по ячейке памяти (указателю).Доступ к a[3] можно найти в постоянном времени, поскольку это просто location_of_a + 3 * sizeof (int).

В C вы можете увидеть это непосредственно.Помните, что a[3] - это то же самое, что и *(a+3) - что более понятно с точки зрения того, что он делает (разыменование над указателем «3 элемента»).

Answer 2

массив из 10 целочисленных переменных с индексами от 0 до 9 может храниться как 10 слов по адресам памяти 2000, 2004, 2008,… 2036, так что элемент с индексом i имеет адрес 2000 + 4 × i. этот процесс занимает одно умножение и одно сложение. так как эти две операции занимают постоянное время. поэтому мы можем сказать, что доступ может выполняться в постоянное время

Answer 3

Просто чтобы завершить, "какая структура доступна за линейное время?" Структура Linked List доступна в линейном времени. Чтобы получить элемент n, вам нужно пройти через n-1 предыдущие элементы. Вы знаете, как магнитофон или кассету VHS, куда идти до конца кассеты / VHS, вам пришлось долго ждать: -)

Массив больше похож на жесткий диск: каждая точка доступна в «постоянное» время :-)

По этой причине ОЗУ компьютера называется ОЗУ: оперативное запоминающее устройство. Вы можете перейти в любое место, если знаете его адрес, не просматривая всю память до этого места.

Некоторые люди говорили мне, что доступ к HD на самом деле не постоянный (где под доступом я подразумеваю «время, чтобы расположить голову и прочитать один сектор HD»). Я должен сказать, что я не уверен в этом. Я погуглил вокруг, и я не нашел никого, кто бы говорил об этом. Я действительно знаю, что время не является линейным, потому что оно все еще доступно случайным образом. В конце концов, если вы считаете, что HD-доступ недостаточно постоянен для вас (но что такое постоянный доступ к ОЗУ с учетом оптимизации кеша, предварительной выборки, локальности данных и компилятора?), Не стесняйтесь рассматривать предложение as Массив больше похож на USB-накопитель: каждая точка доступна в «постоянное» время: -)

Answer 4

«постоянное время» действительно означает «время, не зависящее от« размера проблемы »».Для «проблемы» «извлечь что-то из контейнера» «размер проблемы» - это размер контейнера.

Доступ к элементу массива занимает в основном одинаковое количество времени (это упрощение) независимо от того,размера контейнера, поскольку для извлечения элемента используется фиксированный набор шагов: вычисляется его местоположение в памяти (это также упрощение), а затем извлекается значение в этом месте в памяти.

Связанный список, например, не может этого сделать, потому что каждая ссылка указывает местоположение следующей.Чтобы найти элемент, вам нужно проработать все предыдущие;в среднем вы проработаете половину контейнера, поэтому размер контейнера, очевидно, имеет значение.

Answer 5

Поскольку массивы хранятся в памяти последовательно.Таким образом, на самом деле, когда вы обращаетесь к массиву [3], вы говорите компьютеру: «Получите адрес памяти начала массива, затем добавьте 3 к нему и затем получите доступ к этому месту».Поскольку добавление занимает постоянное время, то и доступ к массиву!

Answer 6

Массив - это сбор данных аналогичных типов.Таким образом, все элементы будут занимать одинаковое количество памяти. Поэтому, если вы знаете базовый адрес массива и тип данных, которые он содержит, вы можете легко получить элемент Array [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];

Следовательно, его ясно видно, что вы можете получить i-й элемент в постоянное время, если знаете базовый адрес и тип данных, которые он содержит.Пожалуйста, посетите эту ссылку, чтобы узнать больше о структуре данных массива.

Answer 7

Если мы знаем место в памяти, к которому необходимо получить доступ, то этот доступ находится в постоянном времени.В случае массива место в памяти рассчитывается с использованием базового указателя, индекса элемента и размера элемента.Это включает в себя операцию умножения и сложения, которая требует постоянного времени для выполнения.Следовательно, доступ к элементу внутри массива занимает постоянное время.

Answer 8

Массив является последовательным, что означает, что адрес следующего элемента в массиве находится рядом с адресом текущего. Поэтому, если вы хотите получить 5-й элемент массива, вы рассчитываете адрес 5-го элемента, суммируя базовый адрес массива с 5. Этот прямой адрес теперь напрямую используется для получения элемента по этому адресу.

Теперь вы можете задать тот же вопрос здесь: «Как компьютер узнает / получает доступ к вычисленному адресу напрямую?» Это природа и принцип работы компьютерной памяти (ОЗУ). Если вас больше интересует, как ОЗУ обращается к любому адресу в постоянное время, вы можете найти его в любом тексте организации компьютера или просто Google.