minmax_elementの複雑さ

Question

どのようにminmax_elementは一般的に実装されていますか？ N = std :: distance（first、last）の場合、時間複雑度が最大（floor（3/2（N-1））、0）の述語のアプリケーションであることがわかります。

ここで、minmax_elementは、反復可能な要素の範囲（read：containers）内の最小要素と最大要素を見つけることを可能にします。たとえば ：

#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を使用するには、要素ごとに2回の比較が必要で、合計で2回の比較が必要です。 std :: min_elementとstd :: max_elementについても同じです。

リファレンス実装では合計で約3n/2の比較しか必要ありません。原則は簡単です。各ステップで2つの要素を処理します。どちらが小さいかを比較するには、1つの比較が必要です。小さい方を比較する1つの比較、大きい方と大きい方を比較する1つの比較が必要です。 2つの要素ごとに合計3つの比較。