Optymalne losowe sortowanie porównania

Więc wszyscy znamy dolną granicę drzewa na podstawie najgorszego przypadku porównań wykonanych przez (deterministyczny) algorytm sortowania porównań. Nie dotyczy losowego sortowania porównań (jeśli mierzymy oczekiwane porównania dla danych wejściowych w najgorszym przypadku). Na przykład, dla , dolna granica deterministyczna wynosi pięć porównań, ale algorytm randomizowany (losowo permutuje dane wejściowe, a następnie zastosuj sortowanie scalające) działa lepiej, mając porównania dla wszystkich danych . $\lceil\log_2 n!\rceil$ $n=4$ $4\frac{2}{3}$

związany bez pułapów nadal obowiązuje w przypadku losowym za pomocą argumentu teoretyczno-informacyjnego i można go nieco dokręcić do Wynika to z tego, że istnieje optymalny algorytm, który losowo permutuje dane wejściowe, a następnie stosuje (deterministyczne) drzewo decyzyjne, a najlepszym drzewem decyzyjnym (jeśli istnieje) jest drzewo, w którym wszystkie liście znajdują się na dwóch kolejnych poziomach. $\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.$

Co jeśli wiadomo coś o górnych granicach tego problemu? Dla wszystkich losowa liczba porównań (w oczekiwaniu, dla danych wejściowych w najgorszym przypadku, dla najlepszego możliwego algorytmu) jest zawsze zdecydowanie lepsza niż najlepszy algorytm deterministyczny (zasadniczo, ponieważ Nigdy nie jest potęgą dwóch) . Ale o ile lepiej? $n>2$ $n!$

ds.algorithms reference-request sorting

— David Eppstein
źródło

Istnieje losowy algorytm z oczekiwaną liczbą porównań; patrz moja odpowiedź tutaj

l g (n!) + o (n)

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

— Dmytro Taranovsky

Ponieważ twoje pytanie brzmi: „Co wiadomo?” Oto coś:

http://arxiv.org/abs/1307.3033

Daje to średnią analizę przypadku algorytmu Forda-Johnsona. Oczekiwana liczba porównań to dla zaskakująco małej stałej (około 0,05). $\log n! +cn$ $c$

— Pat Morin
źródło

Pat: może mógłbyś mi wyjaśnić, dlaczego ta analiza jest pomocna. Oryginalna analiza pokazuje, że najgorszym przypadkiem porównań jest . Ten pokazuje, że oczekiwana liczba porównań to . Czy jestem zdezorientowany? Wydaje się, że najgorszy przypadek związany jest lepszy niż oczekiwany. Ale autorzy stwierdzają, że najgorszy przypadek jest związany, a następnie podejmują wysiłki, aby udowodnić, że średnia związana przypadek ma ściślejszą stałą. Czy stwierdzili coś złego?

n \log n - 1.415 n

$n\log n-1.415n$

n \log n - 1.399 n

$n\log n-1.399n$

— David Eppstein,

Nie jestem ekspertem, jedynym powodem, dla którego wiem o tym wszystkim, jest John Iacono. Myślę jednak, że ma to związek z fluktuacjami opartymi na tym, jak blisko n jest (4/3 razy) potęga 2. Jeśli spojrzysz na analizę na stronie 71 tutaj, link.springer.com/content/pdf /10.1007%2FBF01934989.pdf , granica -1.415n wydaje się utrzymywać tylko wtedy, gdy n = floor ((4/3) 2 ^ k) dla jakiejś liczby całkowitej k. Może wartość -1.329n związana z Knuth jest najlepsza dla wszystkich n?

— Pat Morin,

Zdecydowanie występują fluktuacje, ale myślałem, że (4/3) 2 ^ k to najgorszy przypadek i lepiej w innych przypadkach.

— David Eppstein,