拜托，有人可以解释一下吗:
如果文档说 STL std::vector finding element speed performace = O(ln(n))， 这是什么意思。
O(ln(n)) - 什么是“O”，我可以在哪里读到它？
我可以在哪里阅读有关其他 STL 容器性能的信息
非常感谢
最佳答案
Big O notation是一种衡量算法如何随着其处理的数据规模增长而扩展的方法。
如果一个 vector 通常是 O(n)，则查找一个元素，当 vector 被排序并且您使用其中一个时，它只是 O(lg(n)) binary search family of algorithms .
每个算法的复杂性在标准和任何引用资料中都有规定(例如上面的 std::lower_bound 链接)。
顺便说一句，ln 是 log，以 e 为底，但所有对数的复杂度都相同，因此即使二分查找仅执行 >lg (log2) 操作从技术上讲它是 O(ln(n)) 是正确的。
关于c++ - STL性能O(ln(n))题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4935017/