批量数组操作比顺序操作更快吗？

Question

说我给出一个数组和函数调用replace：

void replace(from, to, items[]) 

，其任务是在items的元素替换数组元素的范围[from, to)。
我会假设事先知道数组的最大大小，所以我可以确保数组永远不会溢出。

我的问题是，如果我给定的置换（例如，形式(from, to, items)的元素）的列表，有可能是我与比执行每个操作顺序地更快时间复杂度获得最终得到的数组？

换句话说，事先知道操作的顺序有没有什么好处呢，还是比逐一给每个操作（就渐近时间复杂度而言）有什么好处？

注：看起来这个问题很混乱;我做了而不是打算暗示替换给定范围的元素的数量与该范围的大小相同！它可能会更少或更多，从而导致转变，问题的关键在于询问是否事先了解它们可以避免在最坏情况下转移等额外工作。

Answer 1

我想这可能不是你正在发现的，但使用Rope可以缩短时间复杂度。它提供像concat这样的字符串操作，而不用“移动”实际的数组。 （不需要是字符串，任意类型的元素可以用作字母）

根据维基百科（...因为我还没有使用过它），绳是一个balaced二叉树的分段字符串。绳子代表长串连接所有分段的串。 您的replace（）函数可以使用Split（）和Concat（）操作来实现， 这两个操作只需要O（log（n））时间。在这里，我把n代表绳子代表的长绳子的长度。

为了得到正常的数组，可以使用Report（）操作在O（n）时间内转换绳索。

所以答案是：有一个算法比顺序应用字符串操作更快。给数组绳子

所适用的每

• 转换代替绳子工作。每个操作都以O（log（n））运行，并且不会复制实际的数组项目。
• 将处理后的绳索转换为真实数组（这会导致所有物品的复制）。
• 返回它。

Answer 2

它总是线性的，下降到memcpy的水平。加速它的唯一方法是空间交易时间 - 覆盖数组下标运算符，以便from和to之间的元素指向items中的元素而不是原始数组，这在任何情况下都不是一个好的解决方案。