二叉搜索是否具有deque C ++数据结构的对数性能？ [英] Does binary search have logarithmic performance of deque C++ data structure?

问题描述

标准说 std :: binary_search（...）和两个相关的函数 std :: lower_bound（...） / code>和 std :: upper_bound（...）都是O（log n）。因此，假定这些算法在 std :: deque （假设其内容由用户保持排序）上具有O（log n）性能。

The standard says that std::binary_search(...) and the two related functions std::lower_bound(...) and std::upper_bound(...) are O(log n) if the data structure has random access. So, given that, I presume that these algorithms have O(log n) performance on std::deque (assuming its contents are kept sorted by the user).

但是，看来 std :: deque 的内部表示是棘手的（它被分成块），所以我是想知道： std :: deque 是否满足O（log n）搜索的要求。

However, it seems that the internal representation of std::deque is tricky (it's broken into chunks), so I was wondering: does the requirement of O(log n) search hold for std::deque.

推荐答案

是，它仍然适用于 deque ，因为容器需要在常量时间提供对任何元素的访问$ c> vector ）。

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).

这并不能免除您 deque 可以排序。

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

这篇关于二叉搜索是否具有deque C ++数据结构的对数性能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！