0

使用 C++ STL 向量,我们正在构建一个包含 N 个元素的向量,出于某种原因,我们选择将它们插入向量的前面。向量前面的每个元素插入都会强制所有现有元素移位 1。这导致向量元素的 (1+2+3+...+N) 整体移位,即 (N/2)(N +1) 轮班。

我的问题是作者是如何获得 (1+2+3+...N) 的,我认为它应该是 1+1+1..N,因为我们将一个元素移动到一个位置以在一开始就变空?

谢谢!

4

3 回答 3

4

[vector.modifiers]/2(描述vector::insert):

复杂度:复杂度与插入的元素数量加上到向量末端的距离成线性关系。

每次添加元素时,到向量末端的距离都会增加 1。

第一次添加元素,有1个要插入,到末尾的距离为0,所以复杂度是1+0=1。第二次,有1个要插入,到末尾的距离end 是 1,所以复杂度是 1 + 1 = 2。第三次,到 end 的距离是 2,所以复杂度是 1 + 2 = 3。这就是创建 1 + 2 + 3 + ... + 作者描述的 N 模式。

于 2012-05-03T08:36:41.003 回答
1

在插入n时,n向量中当前存在需要移动的元素。

vector<int> values;
for (size_t i = 0; i < N; ++i)
{
     //At this point there are `i` elements in the vector that need to be moved
     //to make room for the new element
     values.insert(values.begin(), 0); 
}
于 2012-05-03T08:30:37.230 回答
0

第一个值被移动 N-1 次,每次插入新值时它都必须移动。第二个值移动了 N-2 次,因为在它之后只添加了 N-2 个值。下一个值被移动 N-3 等等。最后一个值不会移动。

我不知道为什么作者说的是 N 而不是 N-1。但是您感到困惑的原因是,作者计算了单个值的移位,而您计算了涉及多个单个值移位的移位过程的数量。

于 2012-05-03T08:28:14.017 回答