Сложность одновременного нахождения максимума и минимума в массиве

Если в массиве из \(n\ge2\) элементов нужно одновременно найти минимум и максимум только с помощью попарных сравнений, оптимальная сложность в худшем случае равна \(\left\lceil\frac{3n}{2}\right\rceil-2\) сравнениям.1, 2

Оптимальный алгоритм обрабатывает элементы парами: внутри каждой пары сначала определяет меньший и больший элемент, затем меньший сравнивает только с текущим минимумом, а больший — только с текущим максимумом. Для чётного \(n\) получается \(3n/2-2\) сравнений, для нечётного — \(3(n-1)/2\).1

Что важно запомнить
  • Искать минимум и максимум независимо — не оптимально: это требует до \(2n-2\) сравнений.
  • Попарный алгоритм использует одно сравнение внутри пары и ещё по одному сравнению с текущими минимумом и максимумом.
  • Точная оптимальная оценка: \(\left\lceil3n/2\right\rceil-2\).1, 2
  • Для чётного \(n\): \(3n/2-2\). Для нечётного \(n\): \(3(n-1)/2\).
  • Нижняя оценка доказывается в модели сравнений подсчётом кандидатов на минимум и максимум.

Попарный алгоритм

Главная идея — не сравнивать каждый новый элемент и с текущим минимумом, и с текущим максимумом. Сначала элементы разбивают на пары. В каждой паре одним сравнением определяют меньший и больший элементы. После этого меньший элемент может повлиять только на минимум, а больший — только на максимум.

Если \(n\) чётно, первые два элемента сравнивают один раз и используют как начальные минимум и максимум. Остаётся \((n-2)/2\) пар. На каждую такую пару тратят три сравнения: одно внутри пары, одно меньшего элемента с текущим минимумом и одно большего с текущим максимумом. Итого

\(1+3\frac{n-2}{2}=\frac{3n}{2}-2\).1

Если \(n\) нечётно, первый элемент берут одновременно как начальные минимум и максимум. Оставшиеся \(n-1\) элементов образуют \((n-1)/2\) пар, каждая требует три сравнения. Получаем

\(3\frac{n-1}{2}=\left\lceil\frac{3n}{2}\right\rceil-2\).1

Почему меньше сравнений в худшем случае недостаточно

Для нижней оценки достаточно рассмотреть входы с попарно различными элементами. В модели сравнений каждый элемент в начале остаётся кандидатом и на минимум, и на максимум. Чтобы элемент перестал быть кандидатом на максимум, он должен хотя бы один раз проиграть сравнение. Чтобы перестал быть кандидатом на минимум, он должен хотя бы один раз выиграть.

В конце должны остаться ровно один кандидат на максимум и один кандидат на минимум, поэтому нужно устранить всего \(2n-2\) кандидатных статусов. Для строгой нижней оценки используют стратегию противника. Когда сравниваются два элемента, которые ещё сохраняют оба статуса, противник отвечает так, что меньший теряет статус кандидата на максимум, а больший — статус кандидата на минимум. Одним сравнением устраняются два статуса, но после этого оба элемента уже не имеют одновременно двух статусов. Поэтому таких первых «двойных» сравнений может быть не более \(\lfloor n/2\rfloor\). В последующих сравнениях противник выбирает согласованный ответ так, чтобы за одно сравнение устранялся не более чем один ещё нужный кандидатный статус. Например, при сравнении кандидата только на максимум с кандидатом только на минимум первый объявляется большим.

Следовательно, любой алгоритм в худшем случае выполняет не менее

\(\lfloor n/2\rfloor + (2n-2-2\lfloor n/2\rfloor)=2n-2-\lfloor n/2\rfloor=\left\lceil\frac{3n}{2}\right\rceil-2\)

сравнений. Эта нижняя оценка совпадает с числом сравнений попарного алгоритма, поэтому результат оптимален.2

Смысл результата

Асимптотически задача всё равно имеет сложность \(\Theta(n)\), но точный подсчёт сравнений показывает преимущество совместного поиска: вместо почти \(2n\) сравнений достаточно примерно \(1.5n\), и в модели сравнений улучшить этот коэффициент в худшем случае нельзя.

Пример простыми словами

Для \(n=8\) сначала сравнивают первые два элемента и получают начальные минимум и максимум — одно сравнение. Остаются три пары. Каждая требует ещё три сравнения, поэтому всего нужно \(1+3\cdot3=10\) сравнений. Формула даёт тот же результат: \(3\cdot8/2-2=10\).

Для \(n=7\) первый элемент используют как начальные минимум и максимум, а остальные шесть элементов образуют три пары. Получаем \(3\cdot3=9\) сравнений, то есть \(\lceil21/2\rceil-2=9\).

Частые ошибки
  • Считать оптимальной схему, где минимум и максимум ищутся двумя независимыми проходами. Она требует \(2n-2\) сравнений и проигрывает попарному методу.
  • Забывать различие инициализации для чётного и нечётного \(n\). Именно оно даёт точную формулу, а не только оценку порядка \(O(n)\).
  • Доказывать только верхнюю оценку. Чтобы утверждать оптимальность, нужно отдельно показать нижнюю границу \(\lceil3n/2\rceil-2\).

Другие вопросы

Источники

  1. 1 Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms 3rd ed. — Cambridge, MA: MIT Press, 2009. § 9.1 «Minimum and maximum»
  2. 2 Hoffmann M., Matoušek J., Okamoto Y., Zumstein P. Minimum and maximum against k lies Chicago Journal of Theoretical Computer Science, 2012, Article 02, pp. 1–10