STL max_element的复杂性 [英] Complexity of STL max_element

问题描述

因此，根据此处的链接： http://www.cplusplus.com/reference/ algorithm / max_element / ， max_element 函数是O（n），显然对于所有STL容器。它是否正确？应该不是一个集合的O（log n）（作为一个二叉树实现）？

So according to the link here: http://www.cplusplus.com/reference/algorithm/max_element/ , the max_element function is O(n), apparently for all STL containers. Is this correct? Shouldn't it be O(log n) for a set (implemented as a binary tree)?

在一个有点相关的说明，我一直使用cplusplus.com

On a somewhat related note, I've always used cplusplus.com for questions which are easier to answer, but I would be curious what others think of the site.

推荐答案

这是线性的，因为它涉及到每个元素。

It's linear because it touches every element.

使用相同的比较器 甚至可以在集合或其他有序容器上使用它是毫无意义的，因为你可以使用 .rbegin（）在常量时间。

It's pointless to even use it on a set or other ordered container using the same comparator because you can just use .rbegin() in constant time.

如果您不使用相同的比较函数，同样，它必须触及每个元素并且必须至少是线性的。

If you're not using the same comparison function there's no guarantee that the orders will coincide so, again, it has to touch every element and has to be at least linear.

虽然算法可能专用于不同的迭代器类别，但没有办法专门化它们基于是否对迭代器范围进行排序。

Although algorithms may be specialized for different iterator categories there is no way to specialize them base on whether an iterator range is ordered.

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

Most algorithms work on unordered ranges (max_element included), a few require the ranges to be ordered (e.g. set_union, set_intersection) some require other properties for the range (e.g. push_heap, pop_heap).

这篇关于STL max_element的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！