Оптимальная рандомизированная сортировка сравнения

Итак, мы все знаем нижнюю границу дерева сравнения на количество худших случаев сравнений, выполненных (детерминистическим) алгоритмом сортировки сравнений. Это не относится к рандомизированной сортировке сравнения (если мы измеряем ожидаемые сравнения для наихудшего случая). Например, для детерминированная нижняя граница равна пяти сравнениям, но рандомизированный алгоритм (случайным образом переставляет входные данные, а затем применяет сортировку слиянием) лучше, имея $\lceil\log_2 n!\rceil$ $n=4$ сравнения в ожидании для всех входов. $4\frac{2}{3}$

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

k + \frac{2 (n! - 2^{k})}{n!}, where k = ⌊ \log_{2} n! ⌋ .

$k+\frac{2(n!-2^k)}{n!} \text{, where } k=\lfloor\log_2 n!\rfloor.$

Что если что-то известно о верхних оценках этой проблемы? Для всех рандомизированное число сравнений (в ожидании, для входных данных наихудшего случая, для наилучшего возможного алгоритма) всегда строго лучше, чем лучший детерминированный алгоритм (по сути, потому что $n>2$ Никогда не является степенью двойки) , Но насколько лучше? $n!$

ds.algorithms reference-request sorting Дэвид Эппштейн
источник

Существует рандомизированный алгоритм с ожидаемым числом сравнений

; смотрите мой ответ здесь

l g (n!) + o (n)

$\mathrm{lg}(n!)+o(n)$

Дмитрий Тарановский

Поскольку твой вопрос: "Что известно?" Вот что-то:

http://arxiv.org/abs/1307.3033

$\log n! +cn$ $c$

Пэт Морин
источник

n \log n - 1.415 n

$n\log n-1.415n$

n \log n - 1.399 n

$n\log n-1.399n$

Я не эксперт, единственная причина, по которой я знаю обо всем этом, - это Джон Иаконо. Я думаю, однако, что это связано с флуктуациями, основанными на том, насколько близко n к (4/3 раза) степени 2. Если вы посмотрите на анализ на странице 71, link.springer.com/content/pdf /10.1007%2FBF01934989.pdf , граница -1.415n, кажется, сохраняется, только когда n = floor ((4/3) 2 ^ k) для некоторого целого числа k. Может быть, значение -1,329n в Кнуте является лучшим для всех n?

Пэт Морин

Определенно есть колебания, но я думал, что (4/3) 2 ^ k был худшим случаем, и это было лучше для других случаев.

Дэвид Эппштейн

Оптимальная рандомизированная сортировка сравнения

Ответы: