所以根据这里的链接:http://www.cplusplus.com/reference/algorithm/max_element/ ,max_element
函数是 O(n),显然对于所有 STL 容器。这样对吗?一个集合(作为二叉树实现)不应该是 O(log n) 吗?
有点相关的说明,我一直使用 cplusplus.com 来解决更容易回答的问题,但我很好奇其他人对这个网站的看法。
最佳答案
它是线性的,因为它触及每个元素。
即使在集合或其他有序容器上使用它也毫无意义使用相同的比较器,因为您可以在恒定时间内使用.rbegin()
。
如果您没有使用相同的比较函数,则无法保证顺序会一致,因此,同样,它必须触及每个元素并且必须至少是线性的。
虽然算法可能专门用于不同的迭代器类别,但无法根据迭代器范围是否有序来专门化它们。
大多数算法适用于无序范围(包括 max_element
),少数算法要求范围有序(例如 set_union
、set_intersection
)需要范围的其他属性(例如 push_heap
、pop_heap
)。
关于c++ - STL max_element 的复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3313301/