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/