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

Метод нахождения k-го наименьшего значения

В информатике алгоритм выбора — это алгоритм поиска наименьшего значения в наборе упорядоченных значений, например чисел. Значение, которое он находит, называется статистикой четного порядка . Отбор включает в себя как частные случаи проблемы поиска минимального , медианного и максимального элементов в коллекции. Алгоритмы выбора включают в себя быстрый выбор и алгоритм медианы медиан . При применении к набору значений эти алгоритмы требуют линейного времени , что выражается с помощью обозначения большого О. Для данных, которые уже структурированы, возможны более быстрые алгоритмы; В крайнем случае выбор в уже отсортированном массиве требует времени . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle O(1)}$

Постановка задачи

Алгоритм задачи выбора принимает на вход набор значений и число . ${\displaystyle k}$ Он выводит наименьшее из этих значений или, в некоторых версиях задачи, набор наименьших значений. Чтобы это было четко определено, должна быть возможность сортировать значения в порядке от наименьшего к наибольшему; например, это могут быть целые числа , числа с плавающей запятой или какой-либо другой тип объекта с числовым ключом. Однако не предполагается, что они уже отсортированы. Часто алгоритмы выбора ограничиваются моделью вычислений , основанной на сравнении , как в алгоритмах сортировки сравнением , где алгоритм имеет доступ к операции сравнения , которая может определить относительный порядок любых двух значений, но не может выполнять какие-либо другие арифметические действия . операции над этими значениями. ^[1] ${\displaystyle k}$ ${\displaystyle k}$

Чтобы упростить проблему, в некоторых работах по этой проблеме предполагается, что все значения отличны друг от друга [ ^2] или что какой-то последовательный метод разрешения конфликтов использовался для присвоения порядка парам элементов с одинаковым значением друг друга. . Другой вариант постановки задачи касается нумерации упорядоченных значений: является ли наименьшее значение полученным установкой , ${\displaystyle k=0}$ как при нумерации массивов с нуля , или оно получается установкой , ${\displaystyle k=1}$ следуя обычным англоязычным соглашениям для наименьшего, второго -самый маленький и т.д.? Эта статья следует соглашениям, используемым Корменом и др., согласно которым все значения различны, а минимальное значение получается из . ^[2] ${\displaystyle k=1}$

Согласно этим соглашениям максимальное значение среди набора значений получается путем установки . Когда – нечетное число , медиана коллекции получается путем установки . Если число четное, существует два варианта медианы, получаемых округлением выбранного значения в меньшую или большую сторону соответственно: нижняя медиана с и верхняя медиана с . ^[2] ${\displaystyle n}$ ${\displaystyle k=n}$ ${\displaystyle n}$ ${\displaystyle k=(n+1)/2}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k=n/2}$ ${\displaystyle k=n/2+1}$

Алгоритмы

Сортировка и пирамидальная выборка

В качестве базового алгоритма выбор наименьшего значения в наборе значений может выполняться с помощью следующих двух шагов: ${\displaystyle k}$

• Сортировка коллекции
• Если выходные данные алгоритма сортировки представляют собой массив , извлеките его элемент ; в противном случае просмотрите отсортированную последовательность, чтобы найти элемент . ${\displaystyle k}$ ${\displaystyle k}$

Во времени для этого метода преобладает этап сортировки, который требует времени при использовании сортировки сравнения . ^{[2] [3]} Даже когда можно использовать алгоритмы сортировки целых чисел , они обычно медленнее, чем линейное время, которого можно достичь с помощью специализированных алгоритмов выбора. Тем не менее, простота этого подхода делает его привлекательным, особенно когда высокооптимизированная процедура сортировки предоставляется как часть библиотеки времени выполнения, а алгоритм выбора — нет. Для входных данных среднего размера сортировка может быть быстрее, чем алгоритмы неслучайного выбора, из-за меньших постоянных факторов во времени ее выполнения. ^[4] Этот метод также создает отсортированную версию коллекции, которая может быть полезна для других последующих вычислений, в частности для выбора с другими вариантами . ^[3] ${\displaystyle \Theta (n\log n)}$ ${\displaystyle k}$

Для алгоритма сортировки, который генерирует по одному элементу за раз, например сортировки выбором , сканирование может выполняться одновременно с сортировкой, и сортировка может быть прекращена, как только будет найден элемент . Примером этого метода можно считать один из возможных вариантов создания утешительной сетки в турнире с выбыванием одного игрока , в котором команды, проигравшие возможному победителю, играют еще один мини-турнир для определения второго места . ^[5] Применение этой оптимизации к пирамидальной сортировке приводит к созданию алгоритма пирамидальной выборки , который может выбрать наименьшее значение за время . ^[6] Это происходит быстро, когда оно мало по отношению к , но вырождается до при больших значениях , например , при выборе , используемом для нахождения медианы. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(n+k\log n)}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle k}$ ${\displaystyle k=n/2}$

Поворот

Многие методы выбора основаны на выборе специального «поворотного» элемента из входных данных и использовании сравнений с этим элементом для разделения оставшихся входных значений на два подмножества: набор элементов, меньших, чем опорный, и набор элементов, больших, чем стержень. Затем алгоритм может определить, где следует найти наименьшее значение, на основе сравнения с размерами этих наборов. В частности, если , то наименьшее значение находится в , и его можно найти рекурсивно, применив тот же алгоритм выбора к . Если , то наименьшее значение является опорным, и его можно вернуть немедленно. В оставшемся случае наименьшее значение находится в , а точнее, это элемент в позиции . Его можно найти, рекурсивно применив алгоритм выбора, ища значение в этой позиции в . ^[7] ${\displaystyle n-1}$ ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k\leq |L|}$ ${\displaystyle k}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle k=|L|+1}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle R}$ ${\displaystyle k-|L|-1}$ ${\displaystyle R}$ ${\displaystyle R}$

Как и в случае с соответствующим алгоритмом быстрой сортировки на основе поворота , разделение входных данных на и может быть выполнено путем создания новых коллекций для этих наборов или с помощью метода, который разбивает заданный тип данных списка или массива на месте. Подробности различаются в зависимости от того, как представлена ​​входная коллекция . ^[8] Время сравнения опорной точки со всеми остальными значениями составляет . ^[7] Однако методы поворота различаются тем, как они выбирают поворот, что влияет на размер подзадач в каждом рекурсивном вызове. Эффективность этих методов во многом зависит от выбора стержня. Если точка поворота выбрана неудачно, время работы этого метода может быть таким же медленным, как . ^[4] ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$

• Если бы точка поворота находилась точно на медиане входных данных, то каждый рекурсивный вызов имел бы не более половины значений, чем предыдущий вызов, а общее время добавлялось бы в геометрической прогрессии к . ${\displaystyle O(n)}$ Однако нахождение медианы само по себе является проблемой выбора для всего исходного ввода. Попытка найти его с помощью рекурсивного вызова алгоритма выбора приведет к бесконечной рекурсии, поскольку размер задачи не будет уменьшаться при каждом вызове. ^[7]
• Быстрый выбор равномерно случайным образом выбирает опорную точку из входных значений. Его можно описать как алгоритм сокращения и поиска , ^[9] вариант быстрой сортировки с той же стратегией поворота, но где быстрая сортировка выполняет два рекурсивных вызова для сортировки двух подколлекций , а быстрый выбор выполняет только один из этих двух вызовов. Ожидаемое время . _ ^{[2] [7] [9]} Для любой константы вероятность того, что количество сравнений превышает ее, суперэкспоненциально мала в . ^[10] ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle O(n)}$ ${\displaystyle C}$ ${\displaystyle Cn}$ ${\displaystyle C}$
• Алгоритм Флойда-Ривеста , разновидность быстрого выбора, выбирает опорную точку путем случайной выборки подмножества значений данных для некоторого размера выборки , а затем рекурсивно выбирает два элемента несколько выше и ниже положения выборки для использования в качестве опорных точек. При таком выборе вполне вероятно, что он будет зажат между двумя опорными точками, так что после поворота для рекурсивного вызова останется только небольшое количество значений данных между опорными точками. Этот метод позволяет достичь ожидаемого количества сравнений , т.е. ^[11] В своей оригинальной работе Флойд и Ривест утверждали, что этот термин можно сделать таким же маленьким, как с помощью схемы рекурсивной выборки, но правильность их анализа была поставлена ​​​​под сомнение. ^{[12] [13]} Вместо этого более строгий анализ показал, что версия их алгоритма достигает этого срока. ^[14] Хотя обычный анализ как быстрого выбора, так и алгоритма Флойда-Ривеста предполагает использование истинного генератора случайных чисел , была доказана версия алгоритма Флойда-Ривеста, использующая генератор псевдослучайных чисел , засеянный только логарифмическим числом истинных случайных битов. работать в линейном времени с высокой вероятностью. ^[15] ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle rk/n}$ ${\displaystyle k}$ ${\displaystyle n+\min(k,n-k)+o(n)}$ ${\displaystyle o(n)}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n\log n}})}$

Визуализация выбора опорной точки для метода медианы медиан . Каждый набор из пяти элементов показан на рисунке в виде столбца точек, отсортированных по возрастанию сверху вниз. Если их медианы (зеленые и фиолетовые точки в среднем ряду) отсортировать по возрастанию слева направо и в качестве опорной выбрать медиану медиан, то элементы в левом верхнем квадранте будут меньше опорной точки, а элементы в нижнем правом квадранте будут больше, чем поворот, показывая, что многие элементы будут удалены при повороте. ${\displaystyle 3n/10}$ ${\displaystyle 3n/10}$

• Метод медианы медиан разделяет входные данные на наборы из пяти элементов и использует какой-либо другой нерекурсивный метод для нахождения медианы каждого из этих наборов за постоянное время для каждого набора. Затем он рекурсивно вызывает себя, чтобы найти медиану этих медиан. Используя полученную медиану медиан в качестве опорной точки, получается раздел с . Таким образом, задача об элементах сводится к двум рекурсивным задачам об элементах (найти стержень) и не более элементов (после использования стержня). Общий размер этих двух рекурсивных подзадач не превышает , что позволяет анализировать общее время как геометрическую прогрессию, прибавляющую к . В отличие от быстрого выбора, этот алгоритм является детерминированным, а не рандомизированным. ^{[2] [4] [5]} Это был первый известный алгоритм детерминированного выбора с линейным временем, ^[5] и его обычно преподают на курсах по алгоритмам студентов как пример принципа « разделяй и властвуй» , который не делится на две равные подзадачи. ^{[2] [4] [9] [16]} Однако высокие постоянные коэффициенты ограничения по времени делают его на практике медленнее, чем быстрый выбор, ^{[3] [9]} и даже медленнее, чем сортировка входных данных среднего размера. ^[4] ${\displaystyle n/5}$ ${\displaystyle \max(|L|,|R|)\leq 7n/10}$ ${\displaystyle n}$ ${\displaystyle n/5}$ ${\displaystyle 7n/10}$ ${\displaystyle 9n/10}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$
• Гибридные алгоритмы, такие как интроселект, могут использоваться для достижения практической производительности быстрого выбора с возвратом к медианам медиан, гарантирующим время наихудшего случая. ^[17] ${\displaystyle O(n)}$

Заводы

Алгоритмы детерминированного выбора с наименьшим известным числом сравнений, для значений, далеких от или , основаны на концепции фабрик , представленной в 1976 году Арнольдом Шенхаге , Майком Патерсоном и Ником Пиппенгером . ^[18] Это методы, которые создают частичные порядки определенных типов на небольших подмножествах входных значений, используя сравнения для объединения меньших частичных порядков. В качестве очень простого примера: фабрика одного типа может принимать на вход последовательность одноэлементных частичных заказов, сравнивать пары элементов из этих заказов и выдавать на выходе последовательность полностью упорядоченных наборов из двух элементов. Элементы, используемые в качестве входных данных для этой фабрики, могут быть либо входными значениями, которые еще ни с чем не сравнивались, либо «отходными» значениями, произведенными другими фабриками. Целью фабричного алгоритма является объединение различных фабрик, при этом выходные данные одних фабрик поступают на входы других, чтобы в конечном итоге получить частичный порядок, в котором один элемент (наименьший ) больше, чем какой-либо другой . элементы и меньше других других. Тщательное проектирование этих фабрик приводит к созданию алгоритма, который при применении к нахождению медианы использует в большинстве случаев сравнения. Для других значений количество сравнений меньше . ^[19] ${\displaystyle k}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k-1}$ ${\displaystyle n-k}$ ${\displaystyle 2.942n}$ ${\displaystyle k}$

Параллельные алгоритмы

Параллельные алгоритмы отбора изучаются с 1975 года, когда Лесли Валиант представил модель дерева параллельных сравнений для анализа этих алгоритмов и доказал, что в этой модели отбор с использованием линейного числа сравнений требует параллельных шагов даже для выбора минимума или максимума. ^[20] Позже исследователи нашли параллельные алгоритмы пошагового отбора , соответствующие этой границе. ^{[21] [22]} В рандомизированной модели дерева параллельных сравнений можно выполнять выбор за ограниченное количество шагов и линейное количество сравнений . ^[23] В более реалистичной модели вычислений с параллельным ОЗУ , с эксклюзивным доступом к памяти для чтения и исключительной записи, выбор может осуществляться по времени с процессорами, что является оптимальным как по времени, так и по количеству процессоров. ^[24] При одновременном доступе к памяти в целом возможно немного более быстрое параллельное время , ^[25] и термин в ограничении времени можно заменить на . ^[26] ${\displaystyle \Omega (\log \log n)}$ ${\displaystyle O(\log \log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(n/\log n)}$ ${\displaystyle \log n}$ ${\displaystyle \log k}$

Сублинейные структуры данных

Когда данные уже организованы в структуру данных , выбор может быть выполнен за время, сублинейное по количеству значений. В качестве простого случая для данных, уже отсортированных в массиве, выбор элемента может быть выполнен путем одного поиска в массиве за постоянное время. ^[27] Для значений, организованных в двумерный массив размером , с отсортированными строками и столбцами, выбор может выполняться за время или быстрее , если он мал по сравнению с размерами массива . ^{[27] [28]} Для коллекции одномерных отсортированных массивов с элементами меньше, чем выбранный элемент в массиве , время равно . ^[28] ${\displaystyle k}$ ${\displaystyle m\times n}$ ${\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle k_{i}}$ ${\displaystyle i}$ ${\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}$

Выборка из данных в двоичной куче требует времени . ${\displaystyle O(k)}$ Это не зависит от размера кучи и быстрее, чем временная граница, полученная при поиске по принципу «сначала лучшее» . ^{[28] [29]} Этот же метод можно применять в более общем плане к данным, организованным в виде любого типа дерева с кучей (дерева, в котором каждый узел хранит одно значение, в котором родительский элемент каждого некорневого узла имеет меньшее значение, чем его ребенок). Этот метод выполнения выбора в куче применялся к задачам составления списка нескольких решений задач комбинаторной оптимизации, таких как поиск k кратчайших путей во взвешенном графе, путем определения пространства состояний решений в форме неявно определенной кучи . упорядоченное дерево, а затем применить этот алгоритм выбора к этому дереву. ^[30] В другом направлении, алгоритмы выбора линейного времени использовались в качестве подпрограммы в структуре данных приоритетной очереди , связанной с кучей, улучшая время извлечения ее -го элемента из до ; вот повторный логарифм . ^[31] ${\displaystyle n}$ ${\displaystyle O(k\log n)}$ ${\displaystyle k}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log ^{*}n+\log k)}$ ${\displaystyle \log ^{*}n}$

Для набора значений данных, подвергающихся динамическим вставкам и удалениям, дерево статистики заказов дополняет самобалансирующуюся структуру двоичного дерева поиска постоянным объемом дополнительной информации на каждый узел дерева, позволяя вставлять, удалять и выполнять запросы выбора, запрашивающие th элемент . в текущем наборе, чтобы все операции выполнялись за время . ^[2] Выходя за рамки модели сравнения вычислений, можно добиться более быстрого выполнения операции для значений, представляющих собой небольшие целые числа, над которыми разрешены двоичные арифметические операции . ^[32] Невозможно использовать потоковый алгоритм с сублинейной памятью в обоих случаях и решать запросы выбора точно для динамических данных, но скетч count-min можно использовать для приблизительного решения запросов выбора, находя значение, положение которого в порядке упорядочения элементов (если бы они были к ним добавлены) находились бы в пределах шагов , для эскиза, размер которого находится в пределах логарифмических коэффициентов . ^[33] ${\displaystyle k}$ ${\displaystyle O(\log n)}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \varepsilon n}$ ${\displaystyle k}$ ${\displaystyle 1/\varepsilon }$

Нижние границы

Время работы алгоритмов выбора, описанных выше, необходимо, поскольку алгоритму выбора, который может обрабатывать входные данные в произвольном порядке, должно потребоваться столько времени, чтобы просмотреть все свои входные данные. Если какое-либо из его входных значений не сравнивается, это значение может быть тем, которое должно было быть выбрано, и алгоритм может дать неверный ответ. ^[28] Помимо этого простого аргумента, было проведено значительное количество исследований по вопросу точного количества сравнений, необходимых для отбора, как в рандомизированном, так и в детерминированном случаях. ${\displaystyle O(n)}$

Выбор минимума значений требует сравнений, поскольку каждое из невыбранных значений должно быть определено как неминимальное, поскольку оно является наибольшим в каком-либо сравнении, и никакие два из этих значений не могут быть наибольшими в одном и том же сравнении. Тот же аргумент применим симметрично и к выбору максимума. ^[14] ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-1}$

Следующий простейший случай — выбор второго по величине. После нескольких неверных попыток первая точная нижняя оценка для этого случая была опубликована в 1964 году советским математиком Сергеем Кислицыным . Это можно показать, заметив, что выбор второго наименьшего значения также требует различения наименьшего значения от остальных, а также рассмотрев количество сравнений, включающих наименьшее значение, которое выполняет алгоритм для этой задачи. Каждый из элементов, которые сравнивались с наименьшим значением, является кандидатом на второе наименьшее значение, и эти значения должны оказаться больше другого значения при втором сравнении, чтобы исключить их как вторые наименьшие значения. Если значения больше по крайней мере в одном сравнении, а значения больше по крайней мере в двух сравнениях, то всего имеется по меньшей мере сравнений. Аргумент противника , в котором результат каждого сравнения выбирается с целью максимизации (при условии согласованности хотя бы с одним возможным порядком), а не на основе числовых значений данных элементов, показывает, что можно заставить быть по крайней мере . Следовательно, наихудшее количество сравнений, необходимое для выбора второго наименьшего значения , равно 0 , то же самое число, которое было бы получено при проведении турнира с одним выбыванием и второго тура среди значений, проигравших наименьшему значению. Однако ожидаемое количество сравнений алгоритма рандомизированного выбора может быть лучше этой границы; например, выбор второго наименьшего из шести элементов требует в худшем случае семи сравнений, но может быть выполнен с помощью рандомизированного алгоритма с ожидаемым количеством сравнений 6,5. ^[14] ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p-1}$ ${\displaystyle n-1}$ ${\displaystyle p-1}$ ${\displaystyle n+p-2}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \log _{2}n}$ ${\displaystyle n+\lceil \log _{2}n\rceil -2}$

В более общем смысле, выбор -го элемента из требует как минимум сравнений, в среднем случае соответствия количества сравнений алгоритма Флойда-Ривеста до его члена. Аргументация ведется непосредственно в пользу детерминированных алгоритмов с рядом сравнений, усредняемых по всем возможным перестановкам входных значений. ^[1] Согласно принципу Яо , это также применимо к ожидаемому количеству сравнений для рандомизированного алгоритма на его входных данных в худшем случае. ^[34] ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n+\min(k,n-k)-O(1)}$ ${\displaystyle o(n)}$

Для детерминированных алгоритмов было показано, что выбор элемента требует сравнений, где ${\displaystyle k}$ ${\displaystyle {\bigl (}1+H(k/n){\bigr )}n+\Omega ({\sqrt {n}})}$

$${\displaystyle H(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}$$

двоичная функция энтропии . ^[35]по крайней мере , ${\displaystyle (2+\varepsilon )n}$. ^[36] ${\displaystyle \varepsilon \approx 2^{-80}}$

Точное количество сравнений

Нахождение медианы пяти значений с использованием шести сравнений. На каждом шаге сравнения, которые необходимо выполнить дальше, показаны в виде сегментов желтой линии, а диаграмма Хассе найденных на данный момент отношений порядка (меньше = ниже и больше = выше) в виде сегментов синей линии. Уже обнаружено, что красные элементы превышают три других и поэтому не могут быть медианой. Больший из двух элементов в окончательном сравнении является медианой.

Кнут предоставляет следующий треугольник чисел, суммирующий пары и для которого известно точное количество сравнений, необходимое для оптимального алгоритма выбора. В четвертой строке треугольника (начиная с верхней строки) указано количество сравнений для входных значений, а в каждой строке указано количество сравнений, необходимых для выбора наименьшего значения из входных данных такого размера. Строки симметричны, поскольку для выбора наименьшей строки в худшем случае требуется ровно такое же количество сравнений, как и для выбора наибольшей . ^[14] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n=1}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

0

1 1

2 3 2

3 4 4 3

4 6 6 6 4

5 7 8 8 7 5

6 8 10 10 10 8 6

7 9 11 12 12 11 9 7

8 11 12 14 14 14 12 11 8

9 12 14 15 16 16 15 14 12 9

Большую часть, но не все записи в левой половине каждой строки можно найти по формуле

$${\displaystyle n-k+(k-1){\bigl \lceil }\log _{2}(n+2-k){\bigr \rceil }.}$$

Милтона Собеланаименьшего^{[14] [37][14] [38]} ${\displaystyle k}$

Языковая поддержка

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

Стандартная библиотека Pythonheapq.nsmallest (начиная с версии 2.4) включает в себя heapq.nlargestподпрограммы для возврата самых маленьких или самых больших элементов из коллекции в отсортированном порядке. В разных версиях Python для этих подпрограмм используются разные алгоритмы. Начиная с версии Python 3.13, реализация поддерживает двоичную кучу, ограниченную хранением элементов и инициализированную первыми элементами коллекции. Тогда каждый последующий элемент коллекции может заменить самый большой или самый маленький элемент в куче (соответственно для и ), если он меньше или больше этого элемента. Наихудшее время для этой реализации хуже, чем то , которое было бы достигнуто с помощью heapselect. Однако для случайных входных последовательностей, вероятно, будет мало обновлений кучи, и большинство входных элементов обрабатываются только с одним сравнением. ^[39] ${\displaystyle k}$ ${\displaystyle k}$heapq.nsmallestheapq.nlargest ${\displaystyle O(n\log k)}$ ${\displaystyle O(n+k\log n)}$

С 2017 года в Matlab включены функции, которые возвращают максимальные (минимальные) значения вектора, а также их индексы. В документации Matlab не указано, какой алгоритм используют эти функции или каково время их работы. ^[40]maxk()mink() ${\displaystyle k}$

История

Quickselect был представлен без анализа Тони Хоаром в 1965 году ^[41] и впервые проанализирован в техническом отчете 1971 года Дональдом Кнутом . ^[11] Первым известным алгоритмом детерминированного выбора с линейным временем является метод медианы медиан , опубликованный в 1973 году Мануэлем Блюмом , Робертом Флойдом , Воаном Праттом , Роном Ривестом и Робертом Тарджаном . ^[5] Они связывают формулировку проблемы отбора с работой Чарльза Л. Доджсона (более известного как Льюис Кэрролл ), который в 1883 году отметил, что обычный дизайн спортивных турниров с выбыванием одного игрока не гарантирует, что победит второй лучший игрок. второе место, ^{[5] [42]} и работа Хьюго Штайнхауса примерно в 1930 году, который следовал той же мысли, требуя разработать турнирный дизайн, который мог бы гарантировать эту гарантию с минимальным количеством сыгранных игр (то есть сравнений ). ^[5]

Смотрите также

• Геометрическая медиана § Вычисления , алгоритмы многомерного обобщения медиан
• Медианный фильтр , применение алгоритмов поиска медианы при обработке изображений

Рекомендации

1. Кунто, Уолтер; Манро, Дж. Ян (1989). «Средний выбор случая». Журнал АКМ . 36 (2): 270–279. дои : 10.1145/62044.62047 . MR  1072421. S2CID  10947879.
2. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. «Глава 9: Медианы и статистика заказов». Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 213–227. ISBN 0-262-03384-4.; «Раздел 14.1: Динамическая статистика заказов», стр. 339–345.
3. Скиена, Стивен С. (2020). «17.3: Медиана и выбор». Руководство по проектированию алгоритмов . Тексты по информатике (Третье изд.). Спрингер. стр. 514–516. дои : 10.1007/978-3-030-54256-6. ISBN 978-3-030-54255-9. MR  4241430. S2CID  22382667.
4. Эриксон, Джефф (июнь 2019 г.). «1.8: Выбор линейного времени». Алгоритмы. стр. 35–39.
5. Блюм, Мануэль ; Флойд, Роберт В .; Пратт, Воган ; Ривест, Рональд Л .; Тарьян, Роберт Э. (1973). «Сроки выбора» (PDF) . Журнал компьютерных и системных наук . 7 (4): 448–461. дои : 10.1016/S0022-0000(73)80033-9 . МР  0329916.
6. Бродал, Герт Столтинг (2013). «Опрос приоритетных очередей». В Броднике, Андрей; Лопес-Ортис, Алехандро; Раман, Венкатеш; Виола, Альфредо (ред.). Компактные структуры данных, потоки и алгоритмы - статьи в честь Дж. Яна Манро по случаю его 66-летия . Конспекты лекций по информатике. Том. 8066. Спрингер. стр. 150–163. дои : 10.1007/978-3-642-40273-9_11.
7. Кляйнберг, Джон ; Тардос, Ева (2006). «13.5 Рандомизированный разделяй и властвуй: поиск медианы и быстрая сортировка». Алгоритм проектирования . Аддисон-Уэсли. стр. 727–734. ISBN 9780321295354.
8. Например, Кормен и др. используйте раздел массива на месте, в то время как Кляйнберг и Тардос описывают входные данные как набор и используют метод, который разделяет их на два новых набора.
9. Гудрич, Майкл Т .; Тамассия, Роберто (2015). «9.2: Выбор». Разработка алгоритмов и их применение . Уайли. стр. 270–275. ISBN 978-1-118-33591-8.
10. Деврой, Люк (1984). «Экспоненциальные оценки времени работы алгоритма выбора» (PDF) . Журнал компьютерных и системных наук . 29 (1): 1–7. дои : 10.1016/0022-0000(84)90009-6. МР  0761047. Деврой, Люк (2001). «О вероятностном наихудшем времени «найти»» (PDF) . Алгоритмика . 31 (3): 291–303. дои : 10.1007/s00453-001-0046-2. MR  1855252. S2CID  674040.
11. Флойд, Роберт В .; Ривест, Рональд Л. (март 1975 г.). «Ожидаемые сроки отбора». Коммуникации АКМ . 18 (3): 165–172. дои : 10.1145/360680.360691 . S2CID  3064709.См. также «Алгоритм 489: алгоритм SELECT — для поиска наименьшего из элементов», с. 173, дои : 10.1145/360680.360694. ${\displaystyle i}$ ${\displaystyle n}$
12. Браун, Теодор (сентябрь 1976 г.). «Замечание к алгоритму 489». Транзакции ACM в математическом программном обеспечении . 2 (3): 301–304. дои : 10.1145/355694.355704. S2CID  13985011.
13. Постмус, JT; Риннуй Кан, AHG ; Тиммер, GT (1983). «Эффективный метод динамического отбора». Коммуникации АКМ . 26 (11): 878–881. дои : 10.1145/182.358440 . MR  0784120. S2CID  3211474.
14. Кнут, Дональд Э. (1998). «Раздел 5.3.3: Выбор минимального сравнения». Искусство компьютерного программирования, Том 3: Сортировка и поиск (2-е изд.). Аддисон-Уэсли. стр. 207–219. ISBN 0-201-89685-0.
15. Карлофф, Ховард Дж.; Рагхаван, Прабхакар (1993). «Рандомизированные алгоритмы и псевдослучайные числа». Журнал АКМ . 40 (3): 454–476. дои : 10.1145/174130.174132 . MR  1370358. S2CID  17956460.
16. Гурвиц, Хая (1992). «Об обучении алгоритмам нахождения медианы». Транзакции IEEE по образованию . 35 (3): 230–232. Бибкод : 1992ITEdu..35..230G. дои : 10.1109/13.144650.
17. Массер, Дэвид Р. (август 1997 г.). «Алгоритмы интроспективной сортировки и отбора». Программное обеспечение: практика и опыт . Уайли. 27 (8): 983–993. doi :10.1002/(sici)1097-024x(199708)27:8<983::aid-spe117>3.0.co;2-#.
18. Шёнхаге, А .; Патерсон, М .; Пиппенджер, Н. (1976). «Нахождение медианы». Журнал компьютерных и системных наук . 13 (2): 184–199. дои : 10.1016/S0022-0000(76)80029-3. MR  0428794. S2CID  29867292.
19. Дор, Дорит ; Цвик, Ури (1999). «Выбор медианы». SIAM Journal по вычислительной технике . 28 (5): 1722–1758. дои : 10.1137/S0097539795288611. MR  1694164. S2CID  2633282.
20. Валиант, Лесли Г. (1975). «Параллелизм в задачах сравнения». SIAM Journal по вычислительной технике . 4 (3): 348–355. дои : 10.1137/0204030. МР  0378467.
21. Айтай, Миклош ; Комлос, Янош ; Штайгер, В.Л.; Семереди, Эндре (1989). «Оптимальный параллельный выбор имеет сложность ». Журнал компьютерных и системных наук . 38 (1): 125–133. дои : 10.1016/0022-0000(89)90035-4. МР  0990052. ${\displaystyle O(\log \log n)}$
22. Азар, Йоси; Пиппенджер, Николас (1990). «Параллельный отбор». Дискретная прикладная математика . 27 (1–2): 49–58. дои : 10.1016/0166-218X(90)90128-Y. МР  1055590.
23. Райщук, Рюдигер (1985). «Вероятностные параллельные алгоритмы сортировки и отбора». SIAM Journal по вычислительной технике . 14 (2): 396–409. дои : 10.1137/0214030. МР  0784745.
24. Хан, Ицзе (2007). «Оптимальный параллельный выбор». Транзакции ACM на алгоритмах . 3 (4): А38:1–А38:11. дои : 10.1145/1290672.1290675. MR  2364962. S2CID  9645870.
25. Чаудхури, Шива; Хагеруп, Торбен; Раман, Раджив (1993). «Приблизительный и точный детерминированный параллельный выбор». В Боржишковском, Анджей М.; Соколовский, Стефан (ред.). Математические основы информатики 1993, 18-й Международный симпозиум, MFCS'93, Гданьск, Польша, 30 августа – 3 сентября 1993 г., Труды . Конспекты лекций по информатике. Том. 711. Спрингер. стр. 352–361. дои : 10.1007/3-540-57182-5_27. hdl : 11858/00-001M-0000-0014-B748-C .
26. Дитц, Пол Ф.; Раман, Раджив (1999). «Малоранговый отбор параллельно с заявками на кучное строительство». Журнал алгоритмов . 30 (1): 33–51. дои : 10.1006/jagm.1998.0971. МР  1661179.
27. Фредериксон, Грег Н.; Джонсон, Дональд Б. (1984). «Обобщенный отбор и ранжирование: отсортированные матрицы». SIAM Journal по вычислительной технике . 13 (1): 14–30. дои : 10.1137/0213002. МР  0731024.
28. Каплан, Хаим; Козма, Ласло; Замир, Ор; Цвик, Ури (2019). «Выбор из кучи, матриц с сортировкой по строкам и использование мягких куч». В Файнмане, Джереми Т.; Митценмахер, Майкл (ред.). 2-й симпозиум по простоте алгоритмов, SOSA 2019, 8–9 января 2019 г., Сан-Диего, Калифорния, США . ОАСИ. Том. 69. Замок Дагштуль – Центр информатики Лейбница. стр. 5:1–5:21. arXiv : 1802.07041 . doi : 10.4230/OASICs.SOSA.2019.5. ${\displaystyle X+Y}$
29. Фредериксон, Грег Н. (1993). «Оптимальный алгоритм выбора в мин-куче». Информация и вычисления . 104 (2): 197–214. дои : 10.1006/inco.1993.1030 . МР  1221889.
30. Эппштейн, Дэвид (1999). «Нахождение кратчайшего пути». SIAM Journal по вычислительной технике . 28 (2): 652–673. дои : 10.1137/S0097539795290477. МР  1634364. ${\displaystyle k}$
31. Бабенко, Максим; Колесниченко Игнат; Смирнов, Иван (2019). «Каскадная куча: к оптимальному по времени извлечению». Теория вычислительных систем . 63 (4): 637–646. дои : 10.1007/s00224-018-9866-1. MR  3942251. S2CID  253740380.
32. Патрашку, Михай ; Торуп, Миккель (2014). «Динамические наборы целых чисел с оптимальным рангом, выбором и поиском предшественников». 55-й Ежегодный симпозиум IEEE по основам компьютерных наук, FOCS 2014, Филадельфия, Пенсильвания, США, 18–21 октября 2014 г. Компьютерное общество IEEE. стр. 166–175. arXiv : 1408.3045 . дои : 10.1109/FOCS.2014.26.
33. Кормод, Грэм; Мутукришнан, С. (2005). «Улучшенная сводка потока данных: эскиз счетчика минут и его приложения». Журнал алгоритмов . 55 (1): 58–75. дои : 10.1016/j.jalgor.2003.12.001. МР  2132028.
34. Чан, Тимоти М. (2010). «Нижние границы выбора во времени и пространстве на основе сравнения». Транзакции ACM на алгоритмах . 6 (2): А26:1–А26:16. дои : 10.1145/1721837.1721842. MR  2675693. S2CID  11742607.
35. Бент, Сэмюэл В.; Джон, Джон В. (1985). «Нахождение медианы требует сравнения». В Седжвике, Роберт (ред.). Материалы 17-го ежегодного симпозиума ACM по теории вычислений, 6–8 мая 1985 г., Провиденс, Род-Айленд, США . Ассоциация вычислительной техники. стр. 213–216. дои : 10.1145/22145.22169 . ${\displaystyle 2n}$
36. Дор, Дорит ; Цвик, Ури (2001). «Медианный отбор требует сравнения». SIAM Journal по дискретной математике . 14 (3): 312–325. дои : 10.1137/S0895480199353895. МР  1857348. ${\displaystyle (2+\varepsilon )N}$
37. Хадиан, Абдолла; Собел, Милтон (май 1969 г.). Выбор -го по величине с использованием двоичного безошибочного сравнения (Отчет). Технические отчеты Школы статистики. Том. 121. Университет Миннесоты. hdl : 11299/199105. ${\displaystyle t}$
38. Гасарч, Уильям ; Келли, Уэйн; Пью, Уильям (июль 1996 г.). «Нахождение большего из меньшего ». Новости ACM SIGACT . 27 (2): 88–96. дои : 10.1145/235767.235772. S2CID  3133332. ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle i,n}$
39. «Исходный код пакета heapq» . Библиотека Python . Проверено 6 августа 2023 г.; см. также связанное сравнение производительности алгоритма на данных наилучшего случая.
40. «Норка: Найдите k наименьших элементов массива» . Документация Matlab R2023a . Математические работы . Проверено 30 марта 2023 г.
41. Хоар, ЦАР (июль 1961 г.). «Алгоритм 65: Найти». Коммуникации АКМ . 4 (7): 321–322. дои : 10.1145/366622.366647.
42. Доджсон, Чарльз Л. (1883). Турниры по лаун-теннису: истинный метод назначения призов с доказательством ошибочности нынешнего метода . Лондон: Макмиллан и Ко.См. также Уилсон, Робин; Моктефи, Амируш, ред. (2019). «Турниры по лаун-теннису». Математический мир Чарльза Л. Доджсона (Льюис Кэрролл) . Издательство Оксфордского университета. п. 129. ИСБН 9780192549013.