Какова временная сложность поиска в ArrayList?

Question

Один вопрос на собеседование, на который я не смог ответить и не смог найти соответствующих ответов в Интернете.

Я знаю, что arraylist извлекает данные в постоянном времени на основе индексов.

Предположим, в массиве данных есть 10000 данных, и элемент находится в 5000-м месте (нам не дано местоположение), мы должны искать определенное значение (например, целое число 3, которое оказывается в 5000-м индексе) , для поиска значения нам придется пройти через массив, чтобы найти значение, и это займет линейное время вправо ??

Потому что, если мы переберем массив, чтобы найти данные, потребуется линейное время, а не постоянное время.

Короче говоря, я хочу знать, как работает метод содержащего объекта, в котором я должен проверить конкретное значение, а у меня нет индекса. Он должен будет пройти через массив, чтобы проверить конкретное значение, и это займет O (n) времени, верно?

Заранее спасибо.

Answer 1

Надеюсь, это то, что вы хотите знать о поиске в ArrayList:

Массивы выкладываются последовательно в память. Это означает, что если это массив целых чисел, который использует 4 байта каждый и начинается с адреса памяти 1000, следующий элемент будет на 1004, а следующий на 1008 и так далее. Таким образом, если я хочу элемент в позиции 20 в моем массиве, код в get () должен будет вычислить:

1000 + 20 * 4 = 1080 

, чтобы иметь точный адрес памяти элемента. Хорошо, ОЗУ получило свое название «Память с произвольным доступом», потому что они построены таким образом, что они имеют иерархию аппаратных мультиплексоров, которые позволяют им получать доступ к любому сохраненному блоку памяти (байту?) В постоянном времени, учитывая адрес.

Таким образом, две простые арифметические операции и один доступ к ОЗУ называются O (1). См. ссылку на оригинальный ответ.