这个代码是O(N)还是O(1)

Question

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)？为什么？

Answer 1

它是O(1)因为它具有恒定的操作数.

Answer 2

正如其他人所说,这是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);

然后它将是O(n),因为vector :: push_back()和vector :: begin()是O(1)并且vector :: push_back()执行n-3次.

Answer 3

它是O(1),因为它的操作数是固定的.对于O(N)来说,执行的操作数量必须存在线性变化.

Answer 4

每个操作都是(摊销)恒定时间,所以整个事情是恒定的时间.