c++ - STL性能O(ln(n))题

Question

拜托，有人可以解释一下吗:

如果文档说 STL std::vector finding element speed performace = O(ln(n))，这是什么意思。

O(ln(n)) - 什么是“O”，我可以在哪里读到它？

我可以在哪里阅读有关其他 STL 容器性能的信息

非常感谢

Answer 1

Big O notation是一种衡量算法如何随着其处理的数据规模增长而扩展的方法。

如果一个 vector 通常是 O(n)，则查找一个元素，当 vector 被排序并且您使用其中一个时，它只是 O(lg(n)) binary search family of algorithms .

每个算法的复杂性在标准和任何引用资料中都有规定(例如上面的 std::lower_bound 链接)。

顺便说一句，ln 是 log，以 e 为底，但所有对数的复杂度都相同，因此即使二分查找仅执行 >lg (log₂) 操作从技术上讲它是 O(ln(n)) 是正确的。