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

Насколько мне известно, не существует алгоритма наихудшего случая, который решает следующую проблему: $O(n)$

Для заданной последовательности длины состоящей из конечных целых чисел, найдите перестановку, где каждый элемент меньше или равен своему преемнику. $n$

Но есть ли доказательство того, что его нет в трансдихотомической модели вычислений ?

Обратите внимание, что я не ограничиваю диапазон целых чисел. Я не ограничиваю решения для сравнений.

complexity-theory sorting computation-models lower-bounds orlp
источник

Насколько я знаю, для SAT может существовать алгоритм времени

! Так что ответ - нет.

O (n)

$O(n)$

Лембик

AFAIK, это все еще открытая проблема.

Юхо

Я не знаю, может ли быть содержательный ответ, пока вы не укажете, какую модель вычислений вы используете, учитывая, что вы не ограничиваете свой компьютер сравнениями и перестановками. С только сравнения RAM и два числа, аргумент от энтропии дает

ограниченные во времени, даже для transdichotomous компьютеров. Тривиально, если вместо свопов и сравнений сортировка является элементарной операцией, это можно сделать в

. Если вставка целого числа в нужное место является элементарной операцией,

Ω (n \cdot l o g (n))

$\Omega(n\cdot log(n))$

Θ (1)

$\Theta(1)$

Θ (n)

$\Theta(n)$ , Была ли у вас в уме конкретная модель, не поддающаяся сравнению?

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen В моем вопросе указывается трансдихотомическая модель вычислений. Простым английским языком: модель вычисления, в которой размер слова машины достаточно велик, чтобы вместить любое целое число задачи. Таким образом, сравнение любых двух целых чисел - это O (1), но также сложение, умножение и т. Д. В этой модели вычислений энтропийная граница уже побита, см. Han, Yijie (2004), «Детерминированная сортировка в O (n log log n) времени и линейном пространстве» .

orlp

@ или я вижу; если вы используете в своих интересах структуру целых чисел, вы можете преодолеть энтропийную границу. Я не знал о целочисленной сортировке; Я обязательно прочитаю на эту тему!

Lieuwe Vinkhuijzen

Ответы:

$O(n)$ $O(1)$ $n$ $[1, n^c]$

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

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

Псевдоним
источник

\log n

$\log n$

O (n)

$O(n)$

@orlp Третий алгоритм в статье говорит о целых числах неограниченной длины.

псевдоним

$c$

Простите, но в его текущем состоянии этот ответ не отвечает на вопрос вообще . Я прямо упомянул, что целые числа не ограничены . Этот ответ решает совершенно другую проблему.

orlp

Финальная точка теперь уже не мелким шрифтом :)

orlp

-1

$O(bn)$ $b$ $n$

Если нет верхней границы для размера ваших целых чисел, то я не верю, что существует какой-либо известный алгоритм линейной сортировки по времени.

RFC 2549
источник

Добро пожаловать! То, что вы говорите, совершенно верно, но я не думаю, что это отвечает на вопрос. Вопрос конкретно требует доказательства того, что требуемый алгоритм не существует в конкретной модели вычислений; просто сказать, что такой алгоритм не известен, не значит, что его не существует.

Дэвид Ричерби

На самом деле, b является константой в нашей задаче, я считаю, что этот алгоритм находится в o (n)

RFC 2549

b

$b$

n

$n$

O (n)

$O(n)$

o (n)

$o(n)$

Да, определенно опечатка;) в его вопросе, поскольку вы предполагаете, что число, подходящее к слову длины b, становится постоянным.

RFC 2549

Это не делает длину слова постоянной. ( В противном случае, не было бы никаких оснований предполагать , явно « что операции на отдельных слов займет постоянное время на операцию».