инициализация массива n элементов с использованием производительности O (1)?

Question

у кого-то есть идея, как я могу это сделать?

спасибо

Answer 1

Если вам нужно что-то сделать с каждым элементом из набора n элементов, вы не сможете сделать это с производительностью лучше, чем O (n).

Answer 2

Если вы имеете в виду «инициализировать плотный массив из N элементов за время, не зависящее от N», то это физически невозможно. Плотный массив имеет пространство для хранения, которое растет линейно с количеством элементов, и для его инициализации потребуется линейное количество времени.

Вы можете иметь инициализацию с постоянным временем, используя разреженный массив. По сути, это ассоциативный массив (или хэш-карта, или словарь, или таблица, в зависимости от языка), который инициализирует элементы при первом обращении к ним.

Answer 3

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

Answer 4

На самом деле, возможно , но только с помощью оборудования. В программном обеспечении вам придется выполнить ряд шагов, пропорциональных n, то есть O(n); однако на аппаратном уровне вы можете связать вещи так, чтобы все элементы массива были установлены параллельно.

Это фактически компромисс между временем и пространством; если раньше требовалось O(n) время, то теперь нужно O(n) элементов схемы, но можно выполнить операцию за O(1) время.

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

Answer 5

Я думаю, это просто вопрос синтаксиса. В C ++ вы можете сделать это:

int foo[1000] = {0};

Все значения в массиве теперь 0

Хотя это выглядит так, как будто выполняется за постоянное время, оно все равно O (n)

Answer 6

Нет. Это физически невозможно. Тем не менее, вы можете использовать векторные инструкции, чтобы сделать это некоторое время O (n * 1 / k), где k - ширина инструкции векторного установщика. Это все еще O (n), но константа уменьшена.