sas*_*740 3 c++ complexity-theory stl
所以根据这里的链接: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).