сложность minmax_element

Question

Как работает minmax_element обычно реализуется? Я вижу, что временная сложность максимальна (пол (3/2 (N-1)), 0) приложения предиката, где N = std :: distance (first, last).

Где minmax_element позволяет мне найти самые маленькие и самые большие элементы в диапазоне элементов, которые могут быть повторены (read: контейнеры). Например:

#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

A reference implementation is given in cppreference.com.

Использование std :: min и std :: max для каждого элемента потребует двух сравнений для каждого элемента или всего двух сравнений. То же самое касается std :: min_element и std :: max_element.

Эталонная реализация требует всего около 3n/2 сравнений. Принцип прост: на каждом шаге мы обрабатываем 2 элемента. Нам нужно одно сравнение, чтобы решить, какой из них меньше, одно сравнение, чтобы сравнить меньшее с минимумом, и одно сравнение для сравнения большего с максимумом. Всего 3 сравнения для каждых 2 элементов.