STL性能O(ln(n))问题

Question

请有人解释一下:

如果文档说STL std :: vector find element performace = O(ln(n)),那是什么意思.

O(ln(n))- 什么是" O ",在哪里我可以读到这个？

在那里我可以阅读其他STL容器性能的性能

非常感谢你

Answer 1

Big O表示法是一种衡量算法如何根据其工作的数据大小进行扩展的方法.

如果通常是向量O(n),则查找元素,仅O(lg(n))在向量排序并且使用二进制搜索系列算法时才进行.

每种算法的复杂性在标准中以及任何参考(例如上面的链接std::lower_bound)中指定.

BTW,ln是log基于e,但所有对数都是相同的复杂性,所以即使二进制搜索只执行lg(log ₂)操作,它在技术上是正确的说它O(ln(n)).

Answer 2

Big-O 表示法是关于程序性能的时间复杂度。

所以 O(ln(n)) 意味着随着向量变大，访问 std::vector 中的元素与 ln(size_of_vector) 成正比，但这仅适用于使用二分搜索的排序向量。二分搜索比线性搜索执行得更快，因为消除可能元素的速度是线性搜索的两倍，因此 ln 实际上是一个以 2 为底的对数。

http://en.wikipedia.org/wiki/Big_O_notation

Answer 3

这被称为Big O表示法,它表示给定算法的渐近复杂性以及与某些参数的关系.

• 渐近意味着我们对前几种情况不感兴趣,但是关于输入参数大小增长时算法的行为.
• 参数取决于要测量的算法
• 我们感兴趣的一项行动

例如,在二分搜索的情况下,我们表示根据我们搜索的集合的大小执行的比较的数量之间的关系.

通常可以从此推断出运行时间,但并非总是如此,特别是如果没有针对实现或硬件约束选择正确的"操作".

几天前有一篇很好的帖子谈到使用磁带作为存储进行排序.因为搜索中的复杂性表达了比较的数量并且使用磁带作为存储,所以运行时主要受到磁带移动的影响......事实证明,尽管被描述为较慢,但是对于快速排序,bubblesort会表现得更好.