сложность valarray

Question

Каковы временные сложности для функций valarray::min и valarray::max в STL?

Кроме того, что может быть хорошим источником информации о пространственно-временных сложностях различных других компонентов 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 почти для каждого метода и функции.

Сложности памяти обычно не указываются ..

Есть веская причина, по которой эти [низкоуровневые] функции не кэшируют результаты min / max:
если вы хотите быстро получить минимальный / максимальный элемент контейнера, который часто изменяется, вы можете
(1) che / поддерживать минимальные / максимальные значения самостоятельно
(2) использовать кучу или деревья вместо вектора

Answer 2

Хорошее место для проверки сложности компонентов STL: http://www.sgi.com/tech/stl/