Подразделы

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

Дата и время

04/04/2025 11:25: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)$ .

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