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)？为什么？
问问题
2980 次
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;
IE：
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 次。
于 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 是恒定时间。恒定时间推送的四个操作是恒定的。设置迭代器是常数时间，因为获取向量的开始是常数，加法是常数。
最后，打印是常数时间，所以整个过程是O(1)。
于 2009-08-12T17:43:09.063 回答
1
它是 O(1)。为了使 O(n) 或 O(not 1) 甚至相关，您需要至少有一个变量（当更改时）将通过更改迭代总数或需要的工作量来影响算法的性能完毕。
于 2009-08-12T17:43:24.367 回答
1
它可以是从 O(1) 到指数的任何值，并且实际上取决于 push_back 的实现。
于 2009-08-12T18:12:02.810 回答
0
只要向量的函数以确定性的方式实现（它们应该是这样或有严重错误），它就是 O(1)。时期。
因为 n 的值是已知的，所以关于向量函数实现的整个讨论是没有实际意义的。此代码段将始终在具有给定向量实现的给定机器上运行完全相同的代码并采用完全相同数量的时钟周期。换掉机器或实现，它仍然是 O(1)；它只需要不同的恒定时间。
请记住，伙计们，O(1) 并不一定意味着“快”。这意味着“非常可扩展”。
于 2009-08-12T19:06:40.313 回答
0
实际上，这取决于 push_back 和 begin 在内部做什么。如果其中一个（或两者）是 O(n)，那么整个事情就是 O(n)，因为 O(N) 支配 O(1)，并且它们的数量是恒定的。任何大于 O(1) 的东西也是如此，例如 O(nlogn)。如果两者都是 O(1)，那么整个事情就是 O(1)，因为它们的数量是恒定的。很可能是 O(1)，因为 push_back 和 begin 通常非常简单并且写成 O(1)。
于 2009-08-12T17:52:30.963 回答
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
你问的是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
它是 O(c)，其中 c 是一个常数，因为没有任何地方是非常数时间操作，但它是 O(1) 吗？我想假设所有这些操作的成本都是 1。
于 2009-08-12T17:44:04.070 回答