c++ - STL max_element 的复杂度

Question

所以根据这里的链接:http://www.cplusplus.com/reference/algorithm/max_element/ ，max_element 函数是 O(n)，显然对于所有 STL 容器。这样对吗？一个集合(作为二叉树实现)不应该是 O(log n) 吗？

有点相关的说明，我一直使用 cplusplus.com 来解决更容易回答的问题，但我很好奇其他人对这个网站的看法。

Answer 1

它是线性的，因为它触及每个元素。

即使在集合或其他有序容器上使用它也毫无意义使用相同的比较器，因为您可以在恒定时间内使用.rbegin()。

如果您没有使用相同的比较函数，则无法保证顺序会一致，因此，同样，它必须触及每个元素并且必须至少是线性的。

虽然算法可能专门用于不同的迭代器类别，但无法根据迭代器范围是否有序来专门化它们。

大多数算法适用于无序范围(包括 max_element)，少数算法要求范围有序(例如 set_union、set_intersection)需要范围的其他属性(例如 push_heap、pop_heap)。