标准说,如果数据结构具有随机访问权限,那么std::binary_search(...)
这两个相关函数std::lower_bound(...)
和std::upper_bound(...)
是 O(log n)。因此,鉴于此,我假设这些算法具有 O(log n) 性能std::deque
(假设其内容由用户保持排序)。
但是,似乎 的内部表示std::deque
很棘手(它被分成块),所以我想知道: O(log n) 搜索的要求是否适用于std::deque
.
标准说,如果数据结构具有随机访问权限,那么std::binary_search(...)
这两个相关函数std::lower_bound(...)
和std::upper_bound(...)
是 O(log n)。因此,鉴于此,我假设这些算法具有 O(log n) 性能std::deque
(假设其内容由用户保持排序)。
但是,似乎 的内部表示std::deque
很棘手(它被分成块),所以我想知道: O(log n) 搜索的要求是否适用于std::deque
.
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.
是的。如果索引存在,则 deque 对索引具有恒定的时间访问权限。它以相同大小的页面组织。你有的是smth。就像一个指向页面的指针向量。如果您有 2 个页面,其中有 100 个元素,并且您想访问第 103 个元素,而不是通过 103/100 = 1 确定页面并通过 103 %100 => 3 确定页面中的索引。现在使用恒定时间访问两个向量来获取元素。
这里来自http://www.cplusplus.com/reference/stl/deque/的声明:
双端队列可以由特定的库以不同的方式实现,但在所有情况下,它们都允许通过随机访问迭代器访问各个元素,并且始终自动处理存储(根据需要扩展和收缩)。
只需编写一个程序来测试一下,我认为双端队列的 binary_search 实现会比向量的慢,但它的复杂度仍然是 O(logn)