Можете ли вы отсортировать n целых чисел в O (n) амортизированной сложности?

Question

Теоретически возможно отсортировать массив из n целых чисел по амортизированной сложности O (n)?

Как насчет попытки создать наихудший вариант сложности O (n)?

Большинство современных алгоритмов построены на O (nlogn) среднем + O (n ^ 2) наихудшем случае. Некоторые из них при использовании большего количества памяти являются O (nlogn) худшими.

Можете ли вы без ограничения использования памяти создать такой алгоритм? Что делать, если ваша память ограничена? как это повредит вашему алгоритму?

Answer 1

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

Некоторые алгоритмы, такие как сортировка по счетчику, сортировка по сегментам или сортировка по основанию, не используют сравнения. Вместо этого они полагаются на свойства самих данных, такие как диапазон значений в данных или размер значения данных.

Эти алгоритмы могут иметь более быстрые сложности. Вот пример сценария:

Вы сортируете 10^6 целых чисел, и каждое целое число находится между 0 и 10. Затем вы можете просто посчитать количество нулей, единиц, двойок и т. Д. И выплюнуть их обратно в отсортированном порядке. Вот как работает контрсортировка, в O(n + m), где m - это число значений, которые может принимать ваш датум (в данном случае, m=11).

Другой:

Вы сортируете 10^6 двоичные строки длиной не более 5 символов. Для этого вы можете использовать основную сортировку: сначала разбейте их на 2 сегмента в зависимости от их первого символа, затем сортируйте их по второму, третьему, четвертому и пятому знакам. Поскольку каждый шаг является стабильной сортировкой, вы должны получить идеально отсортированный список в O(nm), где m - количество цифр или битов в вашей базе данных (в данном случае m=5).

Но в общем случае вы не можете сортировать быстрее, чем O(n lg n) (используя сортировку сравнения).

Answer 2

Я пока не совсем доволен принятым ответом. Поэтому я повторяю ответ:

Возможно ли теоретически отсортировать массив из n целых чисел по амортизированной сложности O (n)?

Ответ на этот вопрос зависит от машины, которая будет выполнять алгоритм сортировки. Если у вас есть машина произвольного доступа, которая может работать ровно с 1 битом, вы можете выполнить radix sort для целых чисел с максимум k битами, что уже было предложено. Таким образом, вы в конечном итоге со сложностью O(kn).
Но если вы работаете на словесном аппарате фиксированного размера с размером слова не менее k бит (что и для всех потребительских компьютеров), лучшее, что вы можете достичь - это O(n log n). Это потому, что либо log n < k, либо вы можете сначала выполнить count sort , а затем выполнить сортировку с помощью алгоритма O (n log n), который также даст первый случай.

А как насчет попытки создать наихудший вариант сложности O (n)?

Это невозможно. Ссылка уже была дана. Идея доказательства состоит в том, что для того, чтобы иметь возможность сортировки, вы должны решить для каждого элемента быть отсортированным, будет ли он больше или меньше любого другого элемента для сортировки. Используя транзитивность, это можно представить в виде дерева решений, которое в лучшем случае имеет n узлов и log n глубину. Поэтому, если вы хотите иметь производительность лучше, чем Ω(n log n), это означает удаление ребер из этого дерева решений. Но если дерево решений не является полным, как вы можете убедиться, что приняли правильное решение по некоторым элементам a и b?

Можете ли вы без ограничений использовать память создать такой алгоритм?

Так как сверху, это невозможно. И поэтому оставшиеся вопросы не имеют отношения к делу.

Answer 3

Если целые числа находятся в ограниченном диапазоне, то их «сортировка» по O (n) будет включать в себя наличие битового вектора из «n» битов ... с циклом по целым числам и установку n% 8 бита смещение n // 8 в этом байтовом массиве в true. Это операция «O (n)». Другой цикл по этому массиву битов для перечисления / перечисления / возврата / печати всех установленных битов также является операцией O (n). (Естественно, O (2n) уменьшается до O (n)).

Это особый случай, когда n достаточно мало, чтобы поместиться в памяти или в файле (с помощью операций поиска ()). Это не общее решение; но он описан в «Программировании жемчужин» Бентли - и якобы был практическим решением реальной проблемы (включая что-то вроде «свободного списка» телефонных номеров ... что-то вроде: найти первый доступный номер телефона, который мог будет выдан новому подписчику).

(Примечание: log (10 * 10) составляет ~ 24 бита для представления каждого возможного целого числа длиной до 10 цифр ... так что в 2 * 31 бита типичного Unix достаточно места) / Linux максимальный размер памяти).

Answer 4

Я полагаю, вы ищете radix sort .