minmax_element的复杂性

Question

minmax_element通常是如何实现的？我可以看到，时间复杂度最多是(底层(3/2(N−1))，0)谓词的应用程序，其中N=std：：距离(首先，最后)。

其中，minmax_element允许我在可以迭代的元素范围内找到最小和最大的元素(阅读:容器)。例如：

#include <algorithm>
#include <vector>
using namespace std;

void Algorithm_minmax_element()
{
    double x = 2, y = 1, z = 0;
    vector<double> v = { 2, 1, 0, -1 };

    auto result1 = minmax(x, y);
    // result1 == pair(1, 2)
    auto result2 = minmax({ x, y, z });
    // result2 == pair(0, 2)
    auto result3 = minmax_element(v.begin(), v.end());
    // result3 == pair(&v[3] = -1, &v[0] = 2)
}

Answer 1

在cppreference.com中给出了一个参考实现。。

对每个元素使用std::min和std::max将需要对每个元素进行两次比较，或总计进行2n比较。std::min_element和std::max_element也是如此。

参考实现总共只需要3n/2的比较。原理很简单:在每一步，我们处理两个元素。我们需要一个比较来决定哪个比较小，一个比较比较小到最小，另一个比较比较大到最大值。每两个元素共进行3次比较。