Выбор на основе разделов
Линейная производительность может быть достигнута с помощью алгоритма выбора на основе разделов, в основном быстрый выбор. Quickselect - это вариант quicksort - в обоих случаях один выбирает точку поворота, а затем разбивает данные по ней, но хотя Quicksort рекурсирует с обеих сторон раздела, Quickselect рекурсирует только с одной стороны, а именно с той стороны, на которой желаемый k-й элемент - это. Как и в случае с быстрой сортировкой, он имеет оптимальную среднюю производительность, в данном случае линейную, но низкую производительность в худшем случае, в данном случае квадратичную. Это происходит, например, взяв первый элемент в качестве опоры и поиска максимального элемента, если данные уже отсортированы. На практике это можно избежать путем выбора случайного элемента в качестве шарнира, что дает почти наверняка линейной характеристики. В качестве альтернативы можно использовать более тщательную детерминированную стратегию поворота, например, медиана медиан. Они объединены в гибридный алгоритм introselect (аналогичный introsort ), который начинается с Quickselect, но возвращается к медиане медиан, если прогресс идет медленно, что приводит как к быстрой средней производительности, так и к оптимальной худшая производительность O (n).
Алгоритмы на основе разделов обычно выполняются на месте, что приводит к частичной сортировке данных. Их можно сделать не к месту, не изменяя исходные данные, за счет O (n) дополнительного места.
Выбор медианы как стратегия поворота
Алгоритм выбора медианы может использоваться для получения общего алгоритма выбора или алгоритма сортировки, применяя его в качестве стратегии поворота в Quickselect или Quicksort; если алгоритм выбора медианы является асимптотически оптимальным (линейное время), результирующий алгоритм выбора или сортировки также. На самом деле точная медиана не требуется - достаточно приблизительной медианы. В алгоритме выбора медианы медиан стратегия поворота вычисляет приблизительную медиану и использует ее как точку поворота, рекурсивно просматривая меньшее множество для вычисления этой точки поворота. На практике накладные расходы на вычисление опорных точек значительны, поэтому эти алгоритмы обычно не используются, но этот метод представляет теоретический интерес для соотнесения алгоритмов выбора и сортировки.
Подробно, учитывая алгоритм выбора медианы, его можно использовать в качестве стратегии поворота в Quickselect, получая алгоритм выбора. Если алгоритм выбора медианы является оптимальным, то есть O (n), то итоговый общий алгоритм выбора также является оптимальным, что опять же означает линейный. Это связано с тем, что Quickselect - это алгоритм разделяй и властвуй, и использование медианы на каждом повороте означает, что на каждом шаге набор поиска уменьшается вдвое, поэтому общая сложность представляет собой геометрическую серию раз сложность каждого шага, и, следовательно, просто постоянная, умноженная на сложность одного шага, на самом деле 
раз (суммируя ряд).
Точно так же, учитывая алгоритм выбора медианы или общий алгоритм выбора, применяемый для поиска медианы, можно использовать его в качестве стратегии поворота в Quicksort, получая алгоритм сортировки. Если алгоритм выбора оптимален, то есть O (n), то полученный алгоритм сортировки является оптимальным, то есть O (n log n). Медиана является лучшим стержнем для сортировки, так как она равномерно делит данные, и таким образом гарантирует оптимальную сортировку, предполагая, что алгоритм выбора является оптимальным. Существует аналог сортировки для медианы медиан, использующий стратегию поворота (приблизительная медиана) в Quicksort, и аналогичный результат дает оптимальную Quicksort.
Инкрементальная сортировка путем выбора
Обратно к выбору путем сортировки, можно поэтапно отсортировать путем повторного выбора. Абстрактно выбор дает только один элемент, k-й элемент. Однако практические алгоритмы выбора часто включают частичную сортировку или могут быть модифицированы для этого. Выбор с помощью частичной сортировки естественным образом делает это, сортировка элементов до k и выбор путем разделения также сортирует некоторые элементы: стержни сортируются в правильные позиции, причем k-й элемент является конечным стержнем, а элементы между стержнями имеют значения между значениями разворота. Разница между выбором на основе разделов и сортировкой на основе разделов, как и в quickselect и quicksort, заключается в том, что при выборе выполняется рекурсия только на одной стороне каждой точки поворота, сортируя только точки поворота (используются в среднем log (n) точек поворота), а не рекурсивно по обе стороны от оси.
Это можно использовать для ускорения последующего выбора тех же данных; в крайнем случае, полностью отсортированный массив допускает выбор O (1). Кроме того, по сравнению с первой выполнением полной сортировки, постепенная сортировка путем повторного выбора амортизирует стоимость сортировки по множественным выборкам.
Для частично отсортированных данных (до k), если записаны частично отсортированные данные и индекс k, до которого они отсортированы, последующие выборки j, меньшего или равного k, можно просто выбрать j-й элемент, поскольку он уже отсортирован, в то время как при выборе j больше k нужно только отсортировать элементы выше k-й позиции.
Для секционированных данных, если список опорных точек сохраняется (например, в отсортированном списке индексов), то последующие выборки необходимо выбирать только в интервале между двумя опорными точками (ближайшие опорные точки ниже и выше). Наибольший выигрыш получают от опорных точек верхнего уровня, которые устраняют дорогостоящие большие разделы: единственная опорная точка около середины данных сокращает время для будущего выбора вдвое. Сводный список будет расти по мере последующего выбора по мере того, как данные становятся более отсортированными, и его даже можно передать в сортировку на основе секций в качестве основы для полной сортировки.
Использование структур данных для выбора в сублинейном времени
Учитывая неорганизованный список данных, для поиска минимального элемента требуется линейное время (Ω (n)), потому что мы должны исследовать каждый элемент (иначе мы можем его пропустить). Если мы организуем список, например, постоянно сохраняя его отсортированным, то выбор k-го по величине элемента тривиален, но тогда для вставки требуется линейное время, как и другие операции, такие как объединение двух списков.
Стратегия поиска статистики порядка в сублинейном времени заключается в хранении данных в организованном виде с использованием подходящих структур данных, которые облегчают выбор. Две такие структуры данных - это древовидные структуры и частотные таблицы.
Когда требуется только минимум (или максимум), хорошим подходом является использование кучи, которая может найти минимальный (или максимальный) элемент за постоянное время, в то время как все другие операции, включая вставку, соответствуют O (log n) или лучше. В более общем смысле, самобалансирующееся двоичное дерево поиска можно легко дополнить, чтобы сделать возможным как вставку элемента, так и поиск k-го по величине элемента за время O (log n); это называется деревом статистики заказов . Мы просто сохраняем в каждом узле количество его потомков и используем его, чтобы определить, по какому пути следовать. Информацию можно эффективно обновлять, поскольку добавление узла влияет только на количество его предков, равное O (log n), а вращения дерева влияют только на количество узлов, участвующих в вращении.
Другая простая стратегия основана на некоторых из тех же концепций, что и хэш-таблица . Когда мы заранее знаем диапазон значений, мы можем разделить этот диапазон на h подинтервалов и назначить их h сегментам. Когда мы вставляем элемент, мы добавляем его в сегмент, соответствующий интервалу, в который он попадает. Чтобы найти минимальный или максимальный элемент, мы просматриваем с начала или до конца в поисках первого непустого сегмента и находим минимальный или максимальный элемент в этом сегменте.. В общем, чтобы найти k-й элемент, мы ведем подсчет количества элементов в каждом сегменте, затем просматриваем сегменты слева направо, складывая счетчики, пока не найдем сегмент, содержащий желаемый элемент, а затем используем ожидаемое линейное время алгоритм, чтобы найти правильный элемент в этом ведре.
Если мы выберем h размером примерно sqrt (n), и вход будет близок к равномерно распределенному, эта схема может выполнять выборки за ожидаемое время O (sqrt (n)). К сожалению, эта стратегия также чувствительна к кластеризации элементов в узком интервале, что может привести к корзинам с большим количеством элементов (кластеризацию можно исключить с помощью хорошей хеш-функции, но найти элемент с k-м наибольшим значением хеш-функции невозможно. очень полезно). Вдобавок, как и в случае с хеш-таблицами, эта структура требует изменения размера таблицы для поддержания эффективности по мере добавления элементов, и n становится намного больше, чем h. Полезный случай этого - нахождение статистики порядка или экстремума в конечном диапазоне данных. Использование приведенной выше таблицы с интервалом корзины 1 и поддержание счетчиков в каждой корзине намного превосходит другие методы. Такие хэш-таблицы похожи на таблицы частот, используемые для классификации данных в описательной статистике.
Нижние границы
в Искусство компьютерного программирования, Дональд Э. Кнут обсудил ряд нижних границ для количества сравнений, необходимых для обнаружения t наименьших записей неорганизованного списка из n элементов (с использованием только сравнений). Существует тривиальная нижняя граница n - 1 для минимального или максимального входа. Чтобы убедиться в этом, рассмотрим турнир, в котором каждая игра представляет собой одно сравнение. Поскольку каждый игрок, кроме победителя турнира, должен проиграть игру, прежде чем мы узнаем победителя, у нас есть нижняя граница n - 1 сравнений.
Для других указателей история становится более сложной. Мы определяем 
как минимальное количество сравнений, необходимое для нахождения t наименьших значений. Кнут ссылается на статью, опубликованную С.С. Кислицыным, в которой показана верхняя граница этого значения:
Эта граница достижима для t = 2, но лучше, более сложные границы известны для больших t.
Сложность пространства
Требуемая сложность пространства для выбора составляет O (1) дополнительного хранилища в дополнение к хранению массива, в котором выполняется выбор. Такая пространственная сложность может быть достигнута при сохранении оптимальной временной сложности O (n).
Алгоритм онлайн-выбора
Онлайн выбор может узко относиться к вычислению k-го наименьшего элемента потока, в этом случае частичного Алгоритмы сортировки - с k + O (1) пространством для k наименьших элементов - могут использоваться, но алгоритмы на основе разделов - нет.
В качестве альтернативы может потребоваться, чтобы сам выбор был онлайн, то есть элемент может быть выбран только из последовательного ввода в случае наблюдения, и каждый выбор, соответственно отказ, является безотзывным. Проблема состоит в том, чтобы выбрать при этих ограничениях конкретный элемент входной последовательности (например, наибольшее или наименьшее значение) с наибольшей вероятностью. Эту проблему можно решить с помощью алгоритма Odds, который дает оптимальное значение при условии независимости; он также является оптимальным как алгоритм с линейным количеством вычислений по длине ввода.
Простейшим примером является задача секретаря выбора максимума с высокой вероятностью, и в этом случае оптимальная стратегия (на случайных данных) состоит в отслеживании текущего максимума первых n / e элементов. и отклоните их, а затем выберите первый элемент, который выше этого максимума.
Связанные проблемы
Можно обобщить проблему выбора для применения к диапазонам в списке, в результате чего возникнет проблема запросов диапазона. Вопрос о запросах медианы диапазона (вычисление медиан нескольких диапазонов) был проанализирован.
Поддержка языков
Очень немногие языки имеют встроенную поддержку общего выбора, хотя многие предоставляют средства для поиска самого маленького или самого большого элемента списка. Заметным исключением является C ++, который предоставляет шаблонный метод nth_elementс гарантией ожидаемого линейного времени, а также разделяет данные, требуя, чтобы n-й элемент был отсортирован в правильное место, элементы перед n-м элементом меньше его, а элементы после n-го элемента больше его. Подразумевается, но не требуется, чтобы он был основан на алгоритме Хоара (или некотором его варианте) в силу требований ожидаемого линейного времени и разделения данных.
Для Perl модуль Sort :: Key :: Top, доступный из CPAN, предоставляет набор функций для выбора первых n элементов из списка с использованием нескольких порядков и пользовательских процедур извлечения ключей. Кроме того, модуль Statistics :: CaseResampling предоставляет функцию для вычисления квантилей с помощью быстрого выбора.
Стандартная библиотека Python (начиная с версии 2.4) включает heapq.nsmallest ()и nlargest (), возвращающие отсортированные списки в O (n log k) time.
Matlab включает функции maxk ()и mink (), которые также возвращают максимальные (минимальные) значения k в векторе. как их индексы.
Поскольку языковая поддержка сортировки более распространена, упрощенный подход сортировки с последующим индексированием предпочтителен во многих средах, несмотря на его недостаток в скорости. В самом деле, для ленивых языков этот упрощенный подход может даже обеспечить наилучшую возможную сложность для k наименьших / наибольших отсортированных (с максимальным / минимальным как частный случай), если сортировка достаточно ленивая.
См. Также
Ссылки
Внешние ссылки
