Алгоритм выбора

Эта статья включает в себя список общих ссылок , но он остается в основном непроверенным, поскольку в нем отсутствуют соответствующие встроенные ссылки . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Июль 2017 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В информатике , алгоритм выбора является алгоритм для нахождения K - го наименьшего числа в списке или массива ; такое число называется статистикой k- го порядка . Сюда входят случаи нахождения минимального , максимального и медианного элементов. Существуют алгоритмы выбора за время O ( n ) (линейное время в худшем случае), и для структурированных данных возможна сублинейная производительность; в крайнем случае O (1) для массива отсортированных данных. Выбор - это подзадача более сложных задач, таких как ближайший сосед ипроблемы кратчайшего пути . Многие алгоритмы выбора выводятся путем обобщения алгоритма сортировки , и, наоборот, некоторые алгоритмы сортировки могут быть получены как повторное применение выбора.

Простейшим случаем алгоритма выбора является поиск минимального (или максимального) элемента путем итерации по списку с отслеживанием текущего минимума - минимума на данный момент - (или максимума), который можно рассматривать как связанный с сортировкой выбора . И наоборот, самый сложный случай алгоритма выбора - это поиск медианы. Фактически, специализированный алгоритм выбора медианы может использоваться для построения общего алгоритма выбора, например, медианы медианы . Самый известный алгоритм выбора - это quickselect , связанный с быстрой сортировкой ; как и быстрая сортировка, он имеет (асимптотически) оптимальную среднюю производительность, но низкую производительность в наихудшем случае, хотя его можно изменить для обеспечения оптимальной производительности и в худшем случае.

Отбор путем сортировки [ править ]

Путем сортировки списка или массива и последующего выбора желаемого элемента выбор можно свести к сортировке . Этот метод неэффективен для выбора одного элемента, но эффективен, когда необходимо сделать много выборок из массива, и в этом случае требуется только одна начальная дорогостоящая сортировка, за которой следует множество дешевых операций выбора - O (1) для массива , хотя выделение в связанном списке равно O ( n ), даже если оно отсортировано, из-за отсутствия произвольного доступа . В общем, для сортировки требуется время O ( n log n ), где n - длина списка, хотя нижняя граница возможна с помощью несравнительных алгоритмов сортировки, таких как сортировка по основанию исчетная сортировка .

Вместо сортировки всего списка или массива можно использовать частичную сортировку для выбора k наименьших или k наибольших элементов. К - й наименьший (. , Соответственно, к - й наибольший элемент) является то наибольшее (соответственно, наименьший элемент.) Из частично отсортированного списка - это то занимает O (1) для доступа к в массиве и O ( K ) для доступа в список.

Неупорядоченная частичная сортировка [ править ]

Если частичная сортировка ослаблена так, что возвращаются k наименьших элементов, но не по порядку, фактор O ( k log k ) может быть исключен. Требуется дополнительный максимальный выбор (занимающий время O ( k )), но, поскольку он все равно дает асимптотическую сложность O ( n ). Фактически, алгоритмы выбора, основанные на разделах, выдают как k- й наименьший элемент, так и k наименьших элементов (с другими элементами не по порядку). Это можно сделать за время O ( n ) - средняя сложность быстрого выбора и сложность наихудшего случая уточненных алгоритмов выбора на основе разделов.${\ Displaystyle к \ Leq п}$

И наоборот, учитывая алгоритм выбора, можно легко получить неупорядоченную частичную сортировку ( k наименьших элементов, не по порядку) за время O ( n ), перебирая список и записывая все элементы, меньшие, чем k- й элемент. Если в результате получается менее k  - 1 элемента, любые оставшиеся элементы равны k- му элементу. Необходимо соблюдать осторожность, в связи с возможностью равенства элементов: один не должен включать в себя все элементы , меньше или равно в к - й элемент, в качестве элементов больше , чем к - й элемент также может быть равен ему.

Таким образом, неупорядоченная частичная сортировка (наименьшие k элементов, но не упорядоченные) и выбор k- го элемента - очень похожие проблемы. У них не только одинаковая асимптотическая сложность, O ( n ), но и решение одного из них может быть преобразовано в решение другого с помощью простого алгоритма (поиск не более k элементов или фильтрация элементов списка ниже отсечка значения k- го элемента).

Сортировка с частичным выбором [ править ]

Простым примером выбора с помощью частичной сортировки является использование сортировки с частичным выбором .

Очевидный алгоритм линейного времени для поиска минимума (соответственно максимума) - итерация по списку и отслеживание минимального (соответственно максимального) элемента - можно рассматривать как сортировку с частичным выбором, которая выбирает 1 наименьший элемент. Однако многие другие частичные сортировки также сводятся к этому алгоритму для случая k  = 1, например, частичная сортировка кучи.

В более общем смысле, сортировка с частичным выбором дает простой алгоритм выбора, который занимает O ( kn ) времени. Это асимптотически неэффективно, но может быть достаточно эффективным, если k мало, и его легко реализовать. Конкретно, мы просто находим минимальное значение и перемещаем его в начало, повторяя в оставшемся списке, пока мы не накопим k элементов, а затем возвращаем k- й элемент. Вот алгоритм, основанный на частичном выборе:

выбор функции (список [1..n], k) для i от 1 до k minIndex = i minValue = список [i] для j от i + 1 до n делать,  если list [j] <minValue, то minIndex = j minValue = список [j] список подкачки [i] и список [minIndex] список возврата [k]

Выбор по разделам [ править ]

Линейная производительность может быть достигнута с помощью алгоритма выбора на основе разделов, в основном quickselect . Quickselect - это вариант быстрой сортировки - в обоих случаях один выбирает точку поворота, а затем разделяет данные по ней, но в то время как Quicksort рекурсирует с обеих сторон раздела, Quickselect рекурсирует только с одной стороны, а именно со стороны, на которой находится желаемый k- й элемент. . Как и в случае с быстрой сортировкой, он имеет оптимальную среднюю производительность, в данном случае линейную, но низкую производительность в худшем случае, в данном случае квадратичную. Это происходит, например, взяв первый элемент в качестве опоры и поиска максимального элемента, если данные уже отсортированы. На практике этого можно избежать, выбрав случайный элемент в качестве стержня, который дает почти определенныелинейная производительность. В качестве альтернативы можно использовать более тщательную детерминированную стратегию разворота, такую ​​как медиана медиан . Они объединены в гибридном introselect алгоритм (аналог introsort ), который начинается с , но падает Быстрый выбор обратно алгоритм выбора , если прогресс идет медленно, что приводит как к быстрому и средней производительности оптимальным в худшем случае производительности O ( п ).

Алгоритмы на основе разделов обычно выполняются на месте, что приводит к частичной сортировке данных. Их можно сделать не к месту, не изменяя исходные данные, за счет O ( n ) дополнительного места.

Выбор медианы как стратегия поворота [ править ]

Алгоритм выбора медианы можно использовать для получения общего алгоритма выбора или алгоритма сортировки, применяя его в качестве стратегии поворота в Quickselect или Quicksort; если алгоритм выбора медианы является асимптотически оптимальным (линейное время), результирующий алгоритм выбора или сортировки также. На самом деле точная медиана не требуется - достаточно приблизительной медианы. В алгоритме выбора медианы медиан стратегия поворота вычисляет приблизительную медиану и использует ее как точку поворота, рекурсивно просматривая меньший набор для вычисления этой точки поворота. На практике накладные расходы на вычисление опорных точек значительны, поэтому эти алгоритмы обычно не используются, но этот метод представляет теоретический интерес для соотнесения алгоритмов выбора и сортировки.

Подробно, учитывая алгоритм выбора медианы, его можно использовать в качестве стратегии поворота в Quickselect, получая алгоритм выбора. Если алгоритм выбора медианы является оптимальным, то есть O ( n ), то итоговый общий алгоритм выбора также является оптимальным, что опять же означает линейный. Это связано с тем, что Quickselect представляет собой алгоритм «разделяй и властвуй» , и использование медианы на каждом повороте означает, что на каждом шаге набор поиска уменьшается вдвое, поэтому общая сложность представляет собой геометрический ряд, умноженный на сложность каждого шага, и, таким образом, просто постоянная, умноженная на сложность одного шага, фактически умноженная на (суммирование ряда).${\ Displaystyle 2 = 1 / (1- (1/2))}$

Точно так же, учитывая алгоритм выбора медианы или общий алгоритм выбора, применяемый для поиска медианы, можно использовать его в качестве стратегии поворота в 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 сегментам. Когда мы вставляем элемент, мы добавляем его в сегмент, соответствующий интервалу, в который он попадает. Чтобы найти минимальный или максимальный элемент, мы просматриваем с начала или до конца первый непустой сегмент и находим минимальный или максимальный элемент в этом сегменте. . В общем, чтобы найти kth элемент, мы ведем подсчет количества элементов в каждом ведре, затем просматриваем сегменты слева направо, складывая счетчики, пока не найдем ведро, содержащее желаемый элемент, затем используем ожидаемый алгоритм линейного времени, чтобы найти правильный элемент в этом ведре.

Если мы выберем h размером примерно sqrt ( n ), а входные данные будут близки к равномерно распределенным, эта схема сможет выполнять выборки за ожидаемое время O (sqrt ( n )). К сожалению, эта стратегия также чувствительна к кластеризации элементов в узком интервале, что может привести к корзинам с большим количеством элементов (кластеризацию можно исключить с помощью хорошей хеш-функции, но найти элемент с k- м наибольшим значением хеш-функции невозможно. t очень полезно). Кроме того, как и хеш-таблицы, эта структура требует изменения размера таблицы для поддержания эффективности по мере добавления элементов, и n становится намного больше, чем h ^2.. Полезный случай этого - нахождение статистики порядка или экстремума в конечном диапазоне данных. Использование приведенной выше таблицы с интервалом корзины 1 и поддержание счетчиков в каждой корзине намного превосходит другие методы. Такие хэш-таблицы похожи на частотные таблицы, используемые для классификации данных в описательной статистике .

Нижние границы [ править ]

В Искусстве программирования , Дональд Е. Кнут обсудил ряд нижних границ для числа сравнений требуется , чтобы найти т наименьшее из записей неорганизованного списка п элементов ( с использованием только сравнений). Существует тривиальная нижняя граница n - 1 для минимального или максимального входа. Чтобы убедиться в этом, рассмотрим турнир, в котором каждая игра представляет собой одно сравнение. Поскольку каждый игрок, кроме победителя турнира, должен проиграть игру, прежде чем мы узнаем победителя, у нас есть нижняя граница n - 1 сравнений.

Для других индексов история становится более сложной. Мы определяем минимальное количество сравнений, необходимое для нахождения t наименьших значений. Кнут ссылается на статью С.С. Кислицына, в которой показана верхняя граница этого значения:${\ Displaystyle W_ {т} (п)}$

${\ Displaystyle W_ {T} (N) \ Leq N-T + \ Sum _ {N + 1-T <J \ Leq N} \ lceil {\ log _ {2} \, j} \ rceil \ quad {\ text {for}} \, n \ geq t}$

Эта оценка достижима для t = 2, но известны лучшие и более сложные оценки для больших t . ^{[ необходима цитата ]}

Сложность космоса [ править ]

Требуемая пространственная сложность выбора составляет O (1) дополнительного хранилища в дополнение к хранению массива, в котором выполняется выбор. Такая пространственная сложность может быть достигнута при сохранении оптимальной временной сложности O (n). ^[1]

Алгоритм онлайн-выбора [ править ]

Онлайн- выбор может относиться узко к вычислению k- го наименьшего элемента потока, и в этом случае могут использоваться алгоритмы частичной сортировки - с пространством k + O (1) для k наименьших элементов на данный момент -, но алгоритмы на основе разделов не могут быть .

В качестве альтернативы, может потребоваться, чтобы сам выбор был онлайн , то есть элемент может быть выбран только из последовательного ввода в случае наблюдения, и каждый выбор, соответственно отказ, является безотзывным. Проблема состоит в том, чтобы выбрать при этих ограничениях конкретный элемент входной последовательности (например, наибольшее или наименьшее значение) с наибольшей вероятностью. Эту проблему можно решить с помощью алгоритма Odds , который дает оптимальное значение при условии независимости; он также является оптимальным как алгоритм с линейным количеством вычислений по длине ввода.

Самым простым примером является задача секретаря по выбору максимума с высокой вероятностью, и в этом случае оптимальная стратегия (на случайных данных) состоит в том, чтобы отслеживать текущий максимум первых n / e элементов и отклонять их, а затем выбирать первый элемент, который является выше этого максимума.

Связанные проблемы [ править ]

Можно обобщить проблему выбора, применив ее к диапазонам в списке, что приведет к проблеме запросов диапазона . Был проанализирован вопрос о медианных запросах диапазона (вычисление медианы нескольких диапазонов).

Языковая поддержка [ править ]

Очень немногие языки имеют встроенную поддержку общего выбора, хотя многие предоставляют средства для поиска самого маленького или самого большого элемента списка. Заметным исключением является C ++ , который предоставляет шаблонный nth_elementметод с гарантией ожидаемого линейного времени, а также разделяет данные, требуя, чтобы n- й элемент был отсортирован в его правильное место, элементы перед n- м элементом меньше его, и элементы после n- го элемента больше его. Подразумевается, но не требуется, чтобы он был основан на алгоритме Хоара (или некотором его варианте) в силу требований ожидаемого линейного времени и разделения данных. ^{[2] [3]}

Для Perl модуль Sort :: Key :: Top , доступный на CPAN , предоставляет набор функций для выбора первых n элементов из списка с использованием нескольких порядков и пользовательских процедур извлечения ключей. Кроме того, модуль Statistics :: CaseResampling предоставляет функцию для вычисления квантилей с помощью быстрого выбора.

Стандартная библиотека Python (начиная с версии 2.4) включает heapq.nsmallest()и nlargest(), возвращая отсортированные списки за время O ( n log k ). ^[4]

Matlab включает maxk()и mink()функции, которые возвращают максимальные (минимальные) значения k в векторе, а также их индексы.

Поскольку языковая поддержка сортировки более широко распространена, упрощенный подход сортировки с последующим индексированием предпочтителен во многих средах, несмотря на его недостаток в скорости. В самом деле, для ленивых языков этот упрощенный подход может даже достичь максимальной сложности для k наименьших / наибольших отсортированных (с максимальным / минимальным как частный случай), если сортировка достаточно ленивая ^{[ необходима цитата ]} .

См. Также [ править ]

• Порядковая оптимизация

Ссылки [ править ]

Внешние ссылки [ править ]

• « Конспект лекции за 25 января 1996 г .: Статистика выбора и порядка », ICS 161: Разработка и анализ алгоритмов, Дэвид Эппштейн