我知道有 std::set::lower_bound
并且时间复杂度是 O(log)
,我看到 std::lower_bound
在 std::set
上运行时比 std::set::lower_bound
慢得多。
我用谷歌搜索并找到了这个:
http://en.cppreference.com/w/cpp/algorithm/lower_bound http://en.cppreference.com/w/cpp/iterator/advance
所以很明显,因为 std::advance
对于 set::iterator
是线性的,所以整个 std::lower_bound
需要直到 O(n)
。
但是,当我使用它时,它的运行速度比 O(n)
快得多(一些 friend 也这么说),谁能解释为什么或告诉我它不是那样的。
最佳答案
std::lower_bound()
的保证复杂度在非随机访问迭代器上为 O(n)
。如果该算法检测到搜索是在一个有序的关联容器上进行的,它可能会利用树结构可能实现更好的复杂性。我不知道是否有任何实现这样做。
关于c++ - std::lower_bound 与 std::set 的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18170527/