Я считаю, что есть способ найти k-й по величине элемент в несортированном массиве длины n в O (n). Или, возможно, это «ожидаемый» O (N) или что-то. Как мы можем это сделать?
performance
algorithm
big-o
MrDatabase
источник
источник
Ответы:
Это называется нахождением статистики k-го порядка . Существует очень простой рандомизированный алгоритм (называемый быстрой выборкой ), который принимает
O(n)
среднее время, времяO(n^2)
наихудшего случая, и довольно сложный нерандомизированный алгоритм (называемый интроселекцией ), который принимает времяO(n)
наихудшего случая. В Википедии есть информация , но она не очень хорошая.Все, что вам нужно, находится на слайдах PowerPoint. Просто чтобы извлечь основной алгоритм алгоритмаO(n)
наихудшего случая (интроселект):Это также очень подробно описано в книге «Введение в алгоритмы» Cormen et al.
источник
Если вам нужен настоящий
O(n)
алгоритм, а неO(kn)
что-то в этом роде, то вам следует использовать быстрый выбор (в основном это быстрая сортировка, когда вы выбрасываете раздел, который вам не интересен). У моего профессора отличная рецензия с анализом времени выполнения: ( ссылка )Алгоритм QuickSelect быстро находит k-й наименьший элемент из несортированного массива
n
элементов. Это рандомизированный алгоритм , поэтому мы рассчитываем ожидаемое время выполнения в худшем случае .Вот алгоритм.
Каково время работы этого алгоритма? Если противник подбрасывает нам монеты, мы можем обнаружить, что пивот всегда самый большой элемент и
k
всегда равен 1, что дает время пробегаНо если выбор действительно случайный, ожидаемое время работы определяется
где мы делаем не совсем разумное предположение, что рекурсия всегда попадает в большее из
A1
илиA2
.Давайте догадаемся, что
T(n) <= an
для некоторыхa
. Тогда мы получими теперь каким-то образом мы должны получить ужасную сумму справа от знака плюс, чтобы поглотить
cn
слева. Если мы просто свяжем это как , мы получим примерно . Но это слишком много - нет места, чтобы выжать2(1/n) ∑i=n/2 to n an
2(1/n)(n/2)an = an
cn
. Итак, давайте расширим сумму, используя формулу арифметического ряда:где мы используем n как «достаточно большое», чтобы заменить уродливые
floor(n/2)
факторы гораздо более чистыми (и меньшими)n/4
. Теперь мы можем продолжитьпри условии
a > 16c
.Это дает
T(n) = O(n)
. Это ясноOmega(n)
, так что мы получаемT(n) = Theta(n)
.источник
k > length(A) - length(A2)
?A
наA1
иA2
вокруг разворота, мы это знаемlength(A) == length(A1)+length(A2)+1
. Таким образом,k > length(A)-length(A2)
эквивалентноk > length(A1)+1
, что верно, когдаk
где-то вA2
.Быстрый Google по этому вопросу ('kth самый большой массив элементов') возвратил это: http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17
(это было специально для 3d крупнейших)
и этот ответ:
источник
Вам нравится быстрая сортировка. Выберите элемент наугад и пихайте все выше или ниже. В этот момент вы будете знать, какой элемент вы на самом деле выбрали, и если это k-й элемент, который вы сделали, в противном случае вы повторяете с корзиной (выше или ниже), что k-й элемент попадет. Статистически говоря, время требуется, чтобы найти, что k-й элемент растет с n, O (n).
источник
Спутник программиста для анализа алгоритма дает версию , которая является O (п), хотя автор заявляет , что постоянный фактор настолько высок, вы, вероятно , предпочитают наивные сортировки-The-список-то-выберите метод.
Я ответил на письмо вашего вопроса :)
источник
Стандартная библиотека C ++ имеет почти такой же вызов функции
nth_element
, хотя и изменяет ваши данные. Он ожидал линейного времени выполнения O (N) и также выполняет частичную сортировку.источник
Хотя не совсем уверен насчет сложности O (n), но он обязательно будет между O (n) и nLog (n). Также обязательно быть ближе к O (n), чем nLog (n). Функция написана на Java
источник
Я реализовал поиск k-го минимума в n несортированных элементах, используя динамическое программирование, в частности метод турниров. Время выполнения O (n + klog (n)). Используемый механизм указан как один из методов на странице Википедии об алгоритме выбора (как указано в одной из публикаций выше). Вы можете прочитать об алгоритме, а также найти код (java) на странице моего блога. Поиск минимума Kth . Кроме того, логика может выполнять частичное упорядочение списка - вернуть первые K min (или max) за O (klog (n)) время.
Хотя предоставленный код приводит к k-му минимуму, аналогичная логика может использоваться для нахождения k-го максимума в O (klog (n)), игнорируя предварительную работу, проделанную для создания дерева турниров.
источник
Вы можете сделать это в O (n + kn) = O (n) (для постоянной k) для времени и O (k) для пространства, отслеживая k самых больших элементов, которые вы видели.
Для каждого элемента в массиве вы можете просмотреть список k самых больших и заменить наименьший элемент новым, если он больше.
Приоритетное решение кучи Уоррена, тем не менее, аккуратнее.
источник
O(n log k)
... все еще вырождающегося в O (nlogn) в случае большого k. Я думаю, что это будет хорошо работать для небольших значений k, однако ... возможно, быстрее, чем некоторые другие алгоритмы, упомянутые здесь [???]Сексуальный быстрый выбор в Python
источник
a1 = [i for i in arr if i > arr[r]]
иa2 = [i for i in arr if i < arr[r]]
, вернем k-й по величине элемент.numpy.sort
fornumpy array
илиsorted
for) можно быстрее, чем использовать эту ручную реализацию.Найдите медиану массива за линейное время, затем используйте процедуру разделения точно так же, как в быстрой сортировке, чтобы разделить массив на две части, значения слева от медианы меньше (<), чем медиана, и справа больше, чем (>) медиана , это тоже может быть сделано во время lineat, теперь, перейдите к той части массива, где лежит k-й элемент, Теперь повторение становится: T (n) = T (n / 2) + cn, что дает мне O (n) в целом.
источник
Ниже приведена ссылка на полную реализацию с довольно подробным объяснением того, как работает алгоритм поиска K-го элемента в несортированном алгоритме. Основная идея заключается в разделении массива, как в QuickSort. Но для того, чтобы избежать крайних случаев (например, когда на каждом шаге выбирается наименьший элемент, так что алгоритм вырождается во время выполнения O (n ^ 2)), применяется специальный выбор, сводный, называемый алгоритмом медианы медиан. Все решение работает за O (n) время в худшем и в среднем случае.
Вот ссылка на полную статью (речь идет о поиске наименьшего K-го элемента, но принцип поиска K-го наибольшего аналогичен ):
Нахождение Kth самого маленького элемента в несортированном массиве
источник
В соответствии с этой статьей Нахождение K-го по величине элемента в списке из n элементов следующий алгоритм
O(n)
в худшем случае займет время.Анализ: как предложено в оригинальной статье:
Почему размер раздела берется 5, а не 3?
Как упоминалось в оригинальной статье :
Теперь я попытался реализовать вышеупомянутый алгоритм как:
Просто для завершения, другой алгоритм использует очередь приоритетов и требует времени
O(nlogn)
.Оба этих алгоритма могут быть протестированы как:
Ожидаемый результат:
18 18
источник
Как насчет такого рода подхода
Поддержание a
buffer of length k
и atmp_max
, получение tmp_max равно O (k) и выполняется n раз, что-то вродеO(kn)
Это правильно или я что-то упустил?
Хотя он не превосходит средний случай быстрого выбора и худший случай метода средней статистики, но его довольно легко понять и реализовать.
источник
перебрать список. если текущее значение больше, чем сохраненное наибольшее значение, сохраните его как наибольшее значение и увеличьте 1-4 и 5 выпадет из списка. Если нет, сравните его с номером 2 и сделайте то же самое. Повторите, проверяя все 5 сохраненных значений. это должно сделать это в O (N)
источник
я хотел бы предложить один ответ
если мы возьмем первые k элементов и отсортируем их в связанный список из k значений
теперь для любого другого значения, даже для наихудшего случая, если мы сделаем вставку сортировки для остальных значений nk, даже в наихудшем случае число сравнений будет k * (nk), а для предыдущих значений k, которые будут отсортированы, пусть будет k * (k- 1) так что получается (nk-k), что есть o (n)
ура
источник
Объяснение алгоритма медианы медиан для нахождения k-го наибольшего целого числа из n можно найти здесь: http://cs.indstate.edu/~spitla/presentation.pdf
Реализация в c ++ ниже:
источник
Существует также алгоритм выбора Вирта , который имеет более простую реализацию, чем QuickSelect. Алгоритм выбора Wirth медленнее, чем QuickSelect, но с некоторыми улучшениями он становится быстрее.
Более детально. Используя оптимизацию MODIFIND для Владимира Забродского и выбор центральной точки 3 и уделив некоторое внимание заключительным шагам разделительной части алгоритма, я придумал следующий алгоритм (предположительно названный «LefSelect»):
В тестах, которые я сделал здесь , LefSelect на 20-30% быстрее, чем QuickSelect.
источник
Решение Haskell:
Это реализует медиану медианных решений, используя метод withShape, чтобы определить размер раздела без его фактического вычисления.
источник
Вот реализация C ++ Randomized QuickSelect. Идея состоит в том, чтобы случайным образом выбрать элемент поворота. Чтобы реализовать рандомизированное разделение, мы используем случайную функцию rand (), чтобы сгенерировать индекс между l и r, поменять элемент со случайно сгенерированным индексом на последний элемент и, наконец, вызвать стандартный процесс разделения, который использует последний элемент в качестве pivot.
Наихудшая временная сложность вышеупомянутого решения - все еще O (n2). В худшем случае, рандомизированная функция всегда может выбрать угловой элемент. Ожидаемая временная сложность вышеупомянутого рандомизированного быстрого выбора составляет Θ (n)
источник
Вызовите опрос () k раз.
источник
Это реализация в Javascript.
Если вы отмените ограничение на невозможность изменить массив, вы можете запретить использование дополнительной памяти, используя два индекса для определения «текущего раздела» (в классическом стиле быстрой сортировки - http://www.nczonline.net/blog/2012/ 11/27 / computer-science-in-javascript-quicksort / ).
Если вы хотите проверить, как это работает, вы можете использовать этот вариант:
Остальная часть кода просто для создания игровой площадки:
Теперь проведите тесты несколько раз. Из-за Math.random () он будет выдавать каждый раз разные результаты:
Если вы тестируете его несколько раз, вы можете даже эмпирически увидеть, что число итераций в среднем составляет O (n) ~ = константа * n, и значение k не влияет на алгоритм.
источник
Я придумал этот алгоритм и, кажется, O (n):
Допустим, k = 3, и мы хотим найти третий по величине элемент в массиве. Я бы создал три переменные и сравнил бы каждый элемент массива с минимумом этих трех переменных. Если элемент массива больше нашего минимума, мы заменим переменную min значением элемента. Продолжаем то же самое до конца массива. Минимум наших трех переменных является третьим по величине элементом в массиве.
И, чтобы найти K-й самый большой элемент, нам нужно K переменных.
Пример: (k = 3)
Может кто-нибудь, пожалуйста, просмотрите это и дайте мне знать, что мне не хватает?
источник
Вот реализация предложенного алгоритма eladv (я также поместил здесь реализацию со случайным шарниром):
источник
она похожа на стратегию быстрой сортировки, в которой мы выбираем произвольную опорную точку и выводим меньшие элементы слева и больше справа.
источник
Перейти к концу этой ссылки: ...........
http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/
источник
Вы можете найти k-й наименьший элемент в O (n) времени и постоянном пространстве. Если мы рассмотрим массив только для целых чисел.
Подход заключается в том, чтобы выполнить бинарный поиск в диапазоне значений массива. Если у нас есть min_value и max_value в диапазоне целых чисел, мы можем выполнить двоичный поиск по этому диапазону. Мы можем написать функцию сравнения, которая сообщит нам, является ли любое значение kth-наименьшим или меньше kth-наименьшего или больше kth-наименьшего. Выполняйте бинарный поиск до k-го наименьшего числа
Вот код для этого
Решение класса:
источник
Существует также один алгоритм, который превосходит алгоритм быстрого выбора. Это называется алгоритм Флойд-Ривец (FR) .
Оригинальная статья: https://doi.org/10.1145/360680.360694
Загружаемая версия: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf
Статья в Википедии https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
Я попытался реализовать быстрый выбор и алгоритм FR в C ++. Также я сравнил их со стандартными реализациями библиотеки C ++ std :: nth_element (который в основном представляет собой интроселектный гибрид quickselect и heapselect). Результатом был быстрый выбор, и nth_element работал в среднем сравнительно, но алгоритм FR работал ок. в два раза быстрее по сравнению с ними.
Пример кода, который я использовал для алгоритма FR:
источник
Что бы я сделал, это:
Вы можете просто хранить указатели на первый и последний элемент в связанном списке. Они изменяются только при обновлении списка.
Обновить:
источник
Сначала мы можем построить BST из несортированного массива, который занимает O (n) времени, и из BST мы можем найти k-й наименьший элемент в O (log (n)), который по всем показателям имеет порядок O (n).
источник