arrays - 在线性时间内将未知数量的元素插入动态数组

Question

(这个问题的灵感来自 deque::insert() at index? ，令我惊讶的是我的算法讲座中没有涉及它，而且我也没有发现它在这里的另一个问题中甚至没有在维基百科中提到过:)。我认为这可能是普遍的兴趣，我会自己回答......)

动态数组是一种数据结构，允许在分摊的常数时间内在末尾添加元素 O(1)(每次需要增长时将分配的内存大小加倍，参见 Amortized time of dynamic array进行简短分析)。

但是，在数组中间插入单个元素需要线性时间 O(n)，因为在最坏的情况下(即在第一个位置插入)所有其他元素都需要移动一个。

如果我想在数组中的特定索引处插入 k 元素，执行插入操作 k 次的天真的方法将导致 的复杂性code>O(n*k)，如果 k=O(n)，则为 O(n²) 的二次复杂度。

如果我事先知道k，解决方案就很简单:如果需要扩展数组(可能重新分配空间)，将元素从插入点开始移动k 并简单地复制新元素。

但可能会有这样的情况，我事先不知道要插入的元素数量:例如，我可能从类似流的接口(interface)中获取元素，所以我只在最后一个元素是阅读。

有没有一种方法可以将多个 (k) 元素(其中 k 事先未知)插入线性时间连续位置的动态数组中？

Answer 1

其实是有办法的，而且很简单:

• 首先将所有 k 元素附加到数组的末尾。由于附加一个元素需要 O(1) 时间，因此这将在 O(k) 时间内完成。
• 然后旋转元素到位。如果要在 index 位置插入元素。为此，您需要将子数组 A[pos..n-1] 向右旋转 k 个位置(或 n-pos-k 左侧的位置，这是等效的)。旋转可以通过使用反向操作在线性时间内完成，如 Algorithm to rotate an array in linear time 中所述。 .因此旋转所需的时间是O(n)。

因此算法的总时间是O(k)+O(n)=O(n+k)。如果要插入的元素的数量是 n (k=O(n)) 的顺序，你将得到 O(n+n) =O(2n)=O(n) 因此是线性时间。