Временная сложность манипулирования массивами

Question

Пара очень простых вопросов, связанных со сложностью времени, здесь:

1. Какова временная сложность инициализации массива в Java? например,

   int arr[] = new int[5000];

   Я предполагаю, что это O (n), или JVM вызывает какую-то безумную аппаратную магию вуду, которая требует только O (1)?

2. Как насчет вставки или извлечения элементов с использованием индекса массива?

   void setNumber(int number, int arrIndex) {
     arr[arrIndex] = number;
   }
   
   int getNumber(int arrIndex) {
     return arr[arrIndex];
   }
   

   Я предполагаю, что это будет O (1). Но, скажем, если arrIndex равен 4999, то указатель, указывающий на начало массива, не вычислит, что элемент, который нужно получить, находится в head + (size of int) * arrIndex и перемещает n (~ 5000) в положение получить этот элемент, таким образом делая сложность O (n), а не O (1).

   Возможно, мы не рассматриваем вещи на аппаратном уровне и удобно называть это «константой», связанной со сложностью времени? Может кто-нибудь уточнить, пожалуйста? Спасибо!

Answer 1

Вы спрашивали о двух вещах, которые обычно O (1).Первый более сложен, чем последний, поэтому я буду обращаться к ним в обратном порядке.

Индексирование массива

Напомним, что «RAM» означает «Память с произвольным доступом»,Это означает, что (кроме эффектов кэширования) доступ к одной части оперативной памяти будет таким же быстрым, как и к любой другой.Это «перемещение» n, на которое вы ссылаетесь, просто не происходит;Схема оперативной памяти спроектирована таким образом, что независимо от того, какие вы установили адресные контакты, будут на выходных контактах следующего цикла.

Распределение памяти

Это осложняется тем фактом, чточто есть распределитель, который делает кучу работы за кулисами.В Википедии содержится огромное количество информации, но в общем (но некрасивом) смысле ответ здесь «O (1), за исключением случаев, когда это не так».

Даже если массив гарантированно был заполнен нулями, вы все равно могли видеть O (1), поскольку многие платформы отображают память, которая уже была заполнена нулями в вашем процессе.Если вам действительно интересно, вы можете взглянуть на реализацию calloc (заполнение нулями) в Malloc Дуга Ли.Конечно, чтобы понять, что происходит ниже, вам понадобится еще одна книга или вам нужно поискать источник ядра .