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）。

Answer 2

对于所有 STL 容器，max_element 函数的复杂度都是 O(n)。

这是不正确的，因为 max_element 适用于迭代器，而不是容器。如果您给它来自集合的迭代器，它无法知道它们来自集合，因此将遍历所有迭代器以查找最大值。所以正确的句子是：

所有前向迭代器的 max_element 函数都是 O(n)

此外，如果您知道自己正在操作一个集合，那么您已经可以使用比 O(n) 更快地提供最大元素的方法，那么为什么要使用 最大元素？

Answer 3

它是一个STL算法，所以它不知道关于容器的任何信息。因此，这种线性搜索是它在前向迭代器上可以做的最好的事情。

Answer 4

STL 算法不知道您从哪个容器中获取迭代器、它是否是有序的以及使用了什么顺序约束。它是一种线性算法，检查范围内的所有元素，同时跟踪迄今为止看到的最大值。

请注意，即使您可以使用元编程技术来检测从中获取迭代器的容器类型，也不能保证您可以跳到最后一个元素来获取最大值：

int values[] = { 1, 2, 3, 4, 5 };
std::set<int, greater<int> > the_set( values, values+5 );
std::max_element( the_set.begin(), the_set.end() ); //??

即使迭代器来自集合，它也是如此。不是最后一个，而是第一个包含最大值的元素。对于更复杂的数据类型，可以使用与最小/最大值无关的其他键对集合进行排序。