1 
vector<int>::iterator it;
vector<int> p;
p.push_back(4);
p.push_back(5);
p.push_back(6);
p.push_back(7);
it = p.begin() + 2;
cout << it << endl;

これO(N)ですかO(1)？なぜ？

4

14 に答える 14

15

一定数の操作があるため、O(1) です。

于 2009-08-12T17:41:30.407 に答える
13

他の人が言ったように、それは O(1) です。ただし、次のように書きたい場合は、次のようになります。

vector<int>::iterator it;
vector<int> p;
p.push_back(4);
p.push_back(5);
p.push_back(6);
p.push_back(7);
...
p.push_back(n);
it = p.begin() + 2;
cout << *it << endl;

すなわち:

for (int i=4;i<=n;i++)
  p.push_back(i);

vector::push_back() と vector::begin() は O(1) で、 vector::push_back() は n-3 回実行されるため、O(n) になります。

于 2009-08-12T18:07:56.843 に答える
9

操作回数が決まっているので O(1) です。何かが O(N) であるためには、実行される操作の数に線形の変動性が必要です。

于 2009-08-12T17:43:33.977 に答える
8

各操作は (償却された) 一定時間なので、全体は一定時間です。

于 2009-08-12T17:43:29.687 に答える
2

対象の操作によって異なりますが、O(1) である必要があります。

ベクトルとイテレータの作成は、メモリ割り当てであるため一定時間です。ベクトルへのプッシュは実装によって一定時間ですが、STL impl は一定時間だと思います。一定時間押し当ての 4 回の動作は一定です。イテレータの設定は一定時間です。これは、ベクトルの開始が一定であり、加算が一定であるためです。

最後に、印刷は一定時間なので、プロセス全体は O(1) です。

于 2009-08-12T17:43:09.063 に答える
1

これは O(1) から指数関数まで何でもかまいませんが、実際には push_back の実装に依存します。

于 2009-08-12T18:12:02.810 に答える
1

O(1)です。O(n) または O(not 1) が適切であるためには、必要な反復または作業の合計量を変更することによって (変更されたときに) アルゴリズムのパフォーマンスに影響を与える少なくとも 1 つの変数が必要です。終わり。

于 2009-08-12T17:43:24.367 に答える
0

最悪の場合、ベクトルへのプッシュは一定時間では発生しません。ベクターがいっぱいの場合は、続行する前にコンテンツをより大きなベクターにコピーします。これはO（n）操作です。

于 2009-08-12T18:02:19.617 に答える
0

私の推測では、あなたはp.begin（）+2について質問していると思います。（ほとんどの人は、たとえば挿入よりも検索に関心があります）。

これは単純なポインタ演算なので、そうです、定数時間O（1）です。これがリンクリストトラバーサルの場合、O（n）になります。もちろん、これは整数ベクトルリストの実装が配列に似ていることを前提としています。つまり、それらはすべてメモリの連続したブロックにあります。

参照：http ：//www.cprogramming.com/tutorial/stl/iterators.html

イテレータは、操作する特定の範囲を指定するのに便利なことがよくあります。たとえば、範囲item.begin（）、item.end（）はコンテナ全体ですが、より小さなスライスを使用できます。これは、他の非常に一般的なクラスのイテレータであるランダムアクセスイテレータを使用すると特に簡単です。ランダムアクセスイテレータは、インクリメントまたはデクリメントできるだけでなく、一定時間で任意の距離を移動できるという意味で、CまたはC++のポインタと機能的に同等です。（たとえば、複数の要素をベクトルの下にジャンプします）。

于 2009-08-12T18:02:22.393 に答える
0

答えは、「+」演算子がどのように機能するかによって異なると思います。単純なポインター演算の場合は O(1) です。

于 2009-08-12T18:08:11.057 に答える
0

ベクトルの関数が決定論的な方法で実装されている限り (そうあるべきか、何かが深刻に間違っている)、それは O(1) です。限目。

ベクトルの関数の実装に関する議論全体は、n の値が既知であるため、意味がありません。このスニペットは、常にまったく同じコードを実行し、特定のベクター実装を備えた特定のマシンでまったく同じ数のクロック サイクルを使用します。マシンまたは実装を交換しても、O(1) のままです。一定の時間がかかるだけです。

皆さん、O(1) は必ずしも「速い」という意味ではないことを覚えておいてください。「非常にスケーラブル」という意味です。

于 2009-08-12T19:06:40.313 に答える
0

実際には、push_back と begin が内部で何を行うかに依存します。どちらか (または両方) が O(n) の場合、O(N) が O(1) を支配し、それらの数が一定であるため、全体が O(n) になります。O(nlogn) など、O(1) より大きいものについても同様です。両方が O(1) の場合、それらの数が一定であるため、全体が O(1) になります。push_back と begin は通常非常に単純で O(1) と書かれているため、おそらく O(1) です。

于 2009-08-12T17:52:30.963 に答える
0

について質問していit = p.begin() + 2;ますか?

この方法でのベクトルの要素へのアクセスは、 と同じように ( Random Access Iteratorの保証から) 一定時間償却されp[2]ます。したがって、次のようなステートメントit = p.begin() + n;は O(1) です。

N が何であるかを説明せずに O(N) について話すのは正しくありませんが、N が要素の数である配列ルックアップについて話していると仮定しています。cout << *it << endl;また、おそらく最後の行を意味します。

于 2009-08-26T21:19:13.017 に答える
-3

どこにも非一定時間の操作がないため、c が定数である O(c) ですが、O(1) ですか? これらすべての操作のコストは1であると想定されていると思います。

于 2009-08-12T17:44:04.070 に答える