1

标准说,如果数据结构具有随机访问权限,那么std::binary_search(...)这两个相关函数std::lower_bound(...)std::upper_bound(...)是 O(log n)。因此,鉴于此,我假设这些算法具有 O(log n) 性能std::deque(假设其内容由用户保持排序)。

但是,似乎 的内部表示std::deque很棘手(它被分成块),所以我想知道: O(log n) 搜索的要求是否适用于std::deque.

4

3 回答 3

10

Yes it still holds for deque because the container is required to provide access to any element in constant time (just a slightly higher constant than vector).

That doesn't relieve you of the obligation for the deque to be sorted though.

于 2011-06-23T14:24:30.370 回答
1

是的。如果索引存在,则 deque 对索引具有恒定的时间访问权限。它以相同大小的页面组织。你有的是smth。就像一个指向页面的指针向量。如果您有 2 个页面,其中有 100 个元素,并且您想访问第 103 个元素,而不是通过 103/100 = 1 确定页面并通过 103 %100 => 3 确定页面中的索引。现在使用恒定时间访问两个向量来获取元素。

这里来自http://www.cplusplus.com/reference/stl/deque/的声明:

双端队列可以由特定的库以不同的方式实现,但在所有情况下,它们都允许通过随机访问迭代器访问各个元素,并且始终自动处理存储(根据需要扩展和收缩)。

于 2011-06-23T14:33:15.343 回答
0

只需编写一个程序来测试一下,我认为双端队列的 binary_search 实现会比向量的慢,但它的复杂度仍然是 O(logn)

于 2011-06-23T14:25:23.400 回答