Операции массивного массива быстрее, чем последовательные операции?

Question

Скажи мне дают массив, а функция называется replace:

void replace(from, to, items[]) 

, чья работа состоит в том, чтобы заменить элементы массива в диапазоне [from, to) с элементами items.
Я предполагаю, что максимальный размер массива известен заранее, поэтому я могу гарантировать, что массив никогда не будет переполняться.

Мой вопрос, если я дал список замен (например элементы вида (from, to, items)), это возможно для меня, чтобы получить конечный результирующий массив с быстрее временной сложностью в чем выполнять каждую операцию последовательно?

Другими словами, есть ли какое-либо преимущество в знании последовательности операций заблаговременно или это не лучше, чем давать каждую операцию по одному (в терминах асимптотической сложности времени)?

Примечание: Кажется, что вопрос запутан; Я сделал , а не намерены подразумевать, что количество элементов, заменяющих заданный диапазон, совпадает с размером этого диапазона! Это может быть меньше или больше, вызывая сдвиг, и точка вопроса заключалась в том, чтобы спросить, знали ли они заранее, чтобы избежать дополнительной работы, например, сдвига в худшем случае.

Answer 1

Я думаю, что это может быть не то, что вы находите, но использование Rope может сократить временную сложность. Он обеспечивает работу с строкой типа concat без «сдвига» фактического массива. (не обязательно, чтобы быть строкой char. arbitary type of element может использоваться как алфавиты)

Согласно Википедии (... поскольку я еще не использовал ее), Rope представляет собой свернутое бинарное дерево фрагментированной строки , Канат представляет длинную строку, конкатенированную всю фрагментированную строку. Ваша функция replace() может быть реализована с использованием операций Split() и Concat() на канате, обе операции занимают только время O (log (n)). Здесь я помещаю n как длину длинной строки, которую представляет веревка.

Чтобы получить нормальный массив, веревку можно преобразовать в O (n) время с помощью операции Report().

так что ответ: существует алгоритм быстрее, чем секвенциально применяется операция строки.

• новообращенных данный массив к веревке
• применять каждые заменить работу на канате. каждая операция выполняется в O (log (n)) и не копирует фактические элементы массива.
• преобразовать обработанную веревку в реальный массив (это вызывает копирование всех элементов).
• верните его.

Answer 2

Это всегда линейный, до memcpy уровень. Единственный способ ускорить это - время торговли для пространства - переопределить оператор индекса массива так, чтобы элементы между from и to указывали на элементы в items, а не на исходный массив, что ни при каких обстоятельствах не является хорошим решением.