0

C ++ STLベクトルを使用して、N個の要素のベクトルを作成しているため、何らかの理由で、それらをベクトルの前に挿入することにしました。ベクトルの前に要素を挿入するたびに、既存のすべての要素が1だけシフトします。これにより、ベクトル要素の全体的なシフトが（1 + 2 + 3 + ... + N）、つまり（N / 2）（N）になります。 +1）シフト。

私の質問は、作者が（1 + 2 + 3 + ... N）をどのように入手したかということです。最初は空になるように、ある位置で1つの要素を移動しているので、1 + 1 +1..Nにする必要があると思いました。

ありがとう！

4

3 に答える 3

4

From [vector.modifiers]/2（説明vector::insert）：

複雑さ：複雑さは、挿入される要素の数に加えて、ベクトルの終わりまでの距離に比例します。

要素を追加するたびに、ベクトルの末尾までの距離が1ずつ増加します。

初めて要素を追加するときは、挿入する1があり、最後までの距離は0なので、複雑さは1 + 0 = 1です。2回目は、挿入する1があり、終わりは1なので、複雑さは1 + 1 = 2です。3回目は、終わりまでの距離が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回シフトされ、新しい値が挿入されるたびに移動する必要があります。2番目の値はN-2倍だけシフトされます。これは、2番目の値の後にN-2値のみが追加されるためです。次の値はN-3にシフトされます。最後の値はシフトされません。

著者がN-1ではなくNについて話している理由はわかりません。しかし、混乱の理由は、作成者が単一の値のシフトをカウントし、複数の単一の値のシフトを含むシフトプロゼッセの量をカウントするためです。

于 2012-05-03T08:28:14.017 に答える