Подразделы

Другие разделы

Дата и время

05/01/2026 09:39:19

Авторизация

Методы уменьшения размера задачи

Идея методов уменьшения размера задачи Сортировка вставками Поиск в глубину и поиск в ширину Алгоритмы генерации комбинаторных объектов Бинарный поиск Задача поиска фальшивой монеты Задача выбора Онлайновые алгоритмы

Задача выбора

Задача выбора заключается в поиске `k`-то наименьшего
элемента в списке из `n` чисел. Это число называется `k`-ой порядковой статистикой.
При `k = 1` или `k = n` можно просмотреть
весь список в поисках наименьшего или наибольшего элемента.
Более интересен случай, когда `k = |~n//2~|`, т.е. когда надо найти элемент, больший одной
половины элементов списка, и меньший — другой половины.
Эта величина в математической статистике
называется *медиана*. Очевидно, мы можем найти `k`-ый по величине элемент,
отсортировав весь список и выбрав `k`-ый по порядку элемент из отсортированного
списка. Время работы такого алгоритма определяется эффективностью используемого
алгоритма сортировки, т.е. равна `O(n log n)`.

--

Можно предположить, что сортировка всего списка — выполнение лишней работы,
поскольку в задаче не требуется сортировать список, а надо только
указать один-единственный элемент.

Мы уже рассматривали алгоритм разбиения элементов
массива на два подмножества: одно из них содержит элементы, не превышающее
некоторое опорное значение `p`, а второе — элементы, которые не меньше `p`.

Пусть `s` — позиция
разбиения. Если `s = k`, то опорный элемент `p` и есть решением задачи выбора.
Если `s > k`, то `k`-ый наименьший элемент находится в левой части
списка, а если `s < k`, то надо найти `(k -s)`-ый наименьший элемент из правой
части списка. Итак, если мы не получаем решение задачи на данной итерации, то
по крайней мере уменьшаем ее размер и получаем задачу, которая решается таким
же методом.

--

Этот алгоритм должен быть более эффективен, чем быстрая сортировка,
так как работает только с одной частью исходного массива после разбиения,
в то время как быстрая сортировка должна обработать обе части.
Если считать, что разбиение всегда выполняется посредине
остающейся части массива, рекуррентное соотношение для количества сравнений
будет иметь вид:
`C(n) = C(n//2) + (n + 1)`,
решение которого, согласно основной теореме, равно `Theta(n)`.

Хотя на самом деле размер массива уменьшается от одной итерации к другой
непредсказуемым образом (иногда это уменьшение меньше, чем в два раза, иногда — больше),
тщательный математический анализ показывает, что эффективность в среднем
случае будет такой же, как если бы уменьшение размера задачи всякий раз было
ровно в два раза. Другими словами, в среднем мы тоже получаем линейный алгоритм.

В худшем же случае эффективность алгоритма падает до `Theta(n^2)`.

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Методы уменьшения размера задачи

Задача выбора