Предположим, что у меня есть массив:
int a [] = {4,5,7,10,2,3,6}
когда я обращаюсь к элементу, например [3], что происходит на самом деле за сценой? Почему многие книги алгоритмов (например, книга Кормена...) говорят, что это занимает постоянное время?
(Я просто нуб в низкоуровневом программировании, поэтому я хотел бы узнать больше от вас, ребята)
Просто, чтобы быть полным, "к какой структуре обращаются в линейное время?" Структура Связанный список осуществляется через линейное время. Чтобы получить элемент n, вам нужно пройти через n-1 предыдущие элементы. Вы знаете, как магнитофон или кассета VHS, куда идти в конец ленты /VHS, вам пришлось долго ждать: -)
Массив больше похож на жесткий диск: каждая точка доступна в "постоянном" времени:-)
Именно по этой причине ОЗУ компьютера называется оперативной памятью: память произвольного доступа. Вы можете перейти в любое место, если вы знаете его адрес, не перемещая всю память до этого местоположения.
Некоторые люди сказали мне, что доступ HD не на самом деле в постоянное время (где по доступу я имею в виду "время, чтобы поместить голову и прочитать один сектор HD" ). Я должен сказать, что я не уверен в этом. У меня есть googled вокруг, и я не нашел никого, кто говорил об этом. Я знаю, что время не линейно, потому что оно по-прежнему доступно случайно. В конце концов, если вы считаете, что доступ HD для вас не является достаточно постоянным (но тогда, что является постоянным - доступ к ОЗУ?), Учитывая возможность кэширования, предварительной выборки, локализации данных и компилятора?), Не стесняйтесь рассматривать предложение поскольку массив больше похож на USB-диск: каждая точка доступна в "постоянном" времени: -)
Массив, эффективно, известен по памяти (указатель). Доступ к a[3] можно найти в постоянное время, так как это просто location_of_a + 3 * sizeof (int).
В C вы можете видеть это напрямую. Помните, что a[3] - это то же самое, что и *(a+3) - это более понятно с точки зрения того, что он делает (разыменование указателя "3 элемента" ).
массив из 10 целых переменных с индексами от 0 до 9 может храниться как 10 слов в адресах памяти 2000, 2004, 2008,... 2036, так что элемент с индексом я имеет адрес 2000 + 4 × i. этот процесс принимает одно умножение и одно добавление. Поскольку эти две операции занимают постоянное время. Так что мы можем сказать, что доступ может выполняться в постоянное время
Поскольку массивы хранятся в памяти последовательно. Так что, когда вы обращаетесь к массиву [3], вы говорите компьютеру: "Получите адрес памяти начала массива, затем добавьте 3 к нему, затем войдите в это место". Поскольку добавление занимает постоянное время, так же как и доступ к массиву!
"постоянное время" действительно означает "время, которое не зависит от" размера проблемы ". Для" проблемы "" получить что-то из контейнера "" размер проблемы" - это размер контейнера.
Доступ к элементу массива занимает в основном одинаковое количество времени (это упрощение) независимо от размера контейнера, поскольку для извлечения элемента используется фиксированный набор шагов: его расположение в памяти (это также упрощение), и затем извлекается значение в этом месте в памяти.
Связанный список, например, не может этого сделать, потому что каждая ссылка указывает местоположение следующего. Чтобы найти элемент, вам нужно работать через все предыдущие; в среднем, вы будете работать через половину контейнера, поэтому размер контейнера, очевидно, имеет значение.
Массив является последовательным, что означает, что следующий адрес элемента в массиве находится рядом с текущим. Поэтому, если вы хотите получить 5-й элемент массива, вы вычисляете адрес 5-го элемента путем суммирования базового адреса массива с 5. Этот прямой адрес теперь напрямую используется для получения элемента по этому адресу.
Теперь вы можете задать один и тот же вопрос здесь: "Как компьютер знает или обращается к вычисленному адресу напрямую?" Это характер и принцип компьютерной памяти (ОЗУ). Если вас больше интересует, как RAM обращается к любому адресу в постоянное время, вы можете найти его в любом тексте организации организации, или вы можете просто его загрузить.
Массив - это набор похожих типов данных. Таким образом, все элементы будут принимать одинаковый объем памяти. Поэтому, если вы знаете базовый адрес массива и тип данных, которые он содержит, вы можете легко получить элемент 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-й элемент в постоянное время, если знаете базовый адрес и тип данных, которые он хранит. Перейдите по ссылке this, чтобы узнать больше о структуре данных массива.
Если мы знаем местоположение памяти, к которому нужно получить доступ, тогда этот доступ будет в постоянное время. В случае массива местоположение памяти вычисляется с использованием базового указателя, индекса элемента и размера элемента. Это включает операцию умножения и сложения, которая требует постоянного времени для выполнения. Следовательно, доступ к элементу внутри массива занимает постоянное время.