valarray复杂度

Question

STL中valarray::min和valarray::max函数的时间复杂度是多少？

另外，什么是寻找各种其他STL组件的时间/空间复杂性的好来源？

Answer 1

O（N）

这些功能不缓存它们的结果。

在任何stl参考中搜索标题为“复杂性”的部分，例如

http://www.cplusplus.com/reference/algorithm/max_element/

或

http://www.sgi.com/tech/stl/min_element.html
http://www.sgi.com/tech/stl/max_element.html

时间复杂度规范是用于几乎所有方法和功能STL说明书的一部分。

记忆的复杂性通常不指定..

有很好的理由，这些[低级别]功能不缓存最小值/最大值结果：
如果你想迅速获得容器的最小/最大元素经常被修改，则可以
（1）cahe /维持最小值/最大值自己
（2）使用堆或树木代替矢量

Answer 2

一个好地方，检查STL组件的复杂性：http://www.sgi.com/tech/stl/