Min и Max за 1.5n СравненийMin & Max in 1.5n Comparisons

Элементы обрабатываются парами (a[i], a[i+1]). Внутри пары одно сравнение определяет, какой элемент "больше" (кандидат на максимум) и какой "меньше" (кандидат на минимум) — эта информация не пропадает зря, в отличие от наивного подхода, где каждый элемент сравнивается и с текущим минимумом, и с текущим максимумом по отдельности. "Победитель" пары сравнивается только с текущим глобальным максимумом (одно сравнение), "проигравший" — только с текущим глобальным минимумом (ещё одно сравнение). Итого на пару элементов уходит 3 сравнения вместо 4 (по 2 на элемент при наивном подходе) — экономия ровно потому, что внутрипарное сравнение выполняет двойную работу: оно же решает, кого дальше сравнивать с максимумом, а кого — с минимумом.Elements are processed in pairs (a[i], a[i+1]). Within a pair, one comparison determines which element is "larger" (a max candidate) and which is "smaller" (a min candidate) — this information isn't wasted, unlike the naive approach where every element is compared against both the current min and the current max separately. The pair's "winner" is compared only against the current global max (one comparison), the "loser" only against the current global min (another comparison). So each pair of elements costs 3 comparisons instead of 4 (2 per element in the naive approach) — the saving comes precisely from the within-pair comparison doing double duty: it's also what decides who gets compared against the max and who against the min.

std::pair<int,int> min_max(const std::vector<int>& a) {
    int n = (int)a.size();
    int mn, mx, i;
    if (n % 2 == 0) {
        if (a[0] < a[1]) { mn = a[0]; mx = a[1]; }  // сравнение №1 (инициализация)// comparison #1 (initialization)
        else { mn = a[1]; mx = a[0]; }
        i = 2;
    } else {
        mn = mx = a[0];    // нечётный n — первый элемент без сравнений// odd n — the first element costs no comparisons
        i = 1;
    }
    for (; i < n - 1; i += 2) {
        int smaller, larger;
        if (a[i] < a[i+1]) { smaller = a[i]; larger = a[i+1]; }  // сравнение №1 в паре// comparison #1 in the pair
        else { smaller = a[i+1]; larger = a[i]; }
        if (smaller < mn) mn = smaller;   // сравнение №2// comparison #2
        if (larger > mx) mx = larger;     // сравнение №3// comparison #3
    }
    return {mn, mx};
}

Столбики обрабатываются парами (жёлтая рамка). Оранжевый — текущий известный минимум, синий — текущий известный максимум. Счётчик сравнений сравнивается с наивным подходом (2n-2) справа.Bars are processed in pairs (yellow outline). Orange is the current known minimum, blue is the current known maximum. The comparison counter is shown against the naive approach's count (2n-2) on the right.

Точная формула — 3⌊n/2⌋ сравнений (плюс поправка на 1, если n нечётно), что действительно приближается к 1.5n при больших n. Доказательство оптимальности (нижней границы) использует "состязательный" аргумент: элемент, ни разу не проигравший сравнение, — кандидат на максимум, ни разу не выигравший — кандидат на минимум; можно показать, что любой алгоритм должен потратить минимум ⌈3n/2⌉ - 2 сравнений, чтобы однозначно определить оба множества-кандидата размером 1 (собственно min и max). Это означает, что представленный алгоритм не просто "хорошая эвристика", а асимптотически точное решение задачи с доказанной нижней границей, аналогично тому, как Ω(n log n) в 2.2.1 — не эмпирическое наблюдение, а теорема.The exact formula is 3⌊n/2⌋ comparisons (plus a correction of 1 if n is odd), which indeed approaches 1.5n for large n. The optimality (lower bound) proof uses an "adversary" argument: an element that has never lost a comparison is a max candidate, one that has never won is a min candidate; it can be shown that any algorithm must spend at least ⌈3n/2⌉ - 2 comparisons to uniquely narrow both candidate sets down to size 1 (the actual min and max). This means the algorithm presented here isn't just a "good heuristic" but an asymptotically exact solution with a proven lower bound, much like Ω(n log n) in 2.2.1 isn't an empirical observation but a theorem.