Penyortiran perbandingan acak optimal

Jadi kita semua tahu perbandingan-pohon batas bawah pada jumlah perbandingan terburuk yang dibuat oleh algoritma sortir perbandingan (deterministik). Itu tidak berlaku untuk penyortiran perbandingan acak (jika kita mengukur perbandingan yang diharapkan untuk input kasus terburuk). Misalnya, untuk , batas bawah deterministik adalah lima perbandingan, tetapi algoritma acak (permutasi acak input dan kemudian menerapkan jenis gabungan) tidak lebih baik, memiliki $\lceil\log_2 n!\rceil$ $n=4$ perbandingan untuk semua input. $4\frac{2}{3}$

The terikat tanpa langit-langit masih berlaku dalam kasus acak, dengan argumen informasi-teoretis, dan dapat sedikit diperketat menjadi $\log_2 n!$ Ini mengikuti karena ada algoritma optimal yang secara acak memungkinkan input dan kemudian menerapkan pohon keputusan (deterministik), dan pohon keputusan terbaik (jika ada) adalah pohon di mana semua daun berada dalam dua level berturut-turut.

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.$

Bagaimana jika ada yang diketahui tentang batas atas untuk masalah ini? Untuk semua , jumlah perbandingan acak (dengan harapan, untuk input kasus terburuk, untuk algoritme terbaik) selalu benar-benar lebih baik daripada algoritma deterministik terbaik (pada dasarnya, karena pernah merupakan kekuatan dua) . Tetapi seberapa jauh lebih baik? $n>2$ $n!$

ds.algorithms reference-request sorting David Eppstein
sumber

l g (n!) + o (n)

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

Karena pertanyaan Anda adalah: "Apa yang diketahui?" Ini ada sesuatu:

http://arxiv.org/abs/1307.3033

$\log n! +cn$ $c$

Pat Morin
sumber

n \log n - 1.415 n

$n\log n-1.415n$

n \log n - 1.399 n

$n\log n-1.399n$

Saya bukan ahli, satu-satunya alasan saya tahu tentang semua ini adalah John Iacono. Saya pikir, bagaimanapun, itu ada hubungannya dengan fluktuasi berdasarkan seberapa dekat n adalah (4/3 kali) kekuatan 2. Jika Anda melihat analisis pada halaman 71 di sini, link.springer.com/content/pdf /10.1007%2FBF01934989.pdf , batas -1.415n tampaknya hanya berlaku ketika n = lantai ((4/3) 2 ^ k) untuk beberapa bilangan bulat k. Mungkin -1.329n yang terikat pada Knuth adalah yang terbaik untuk semua n?

Pat Morin

Jelas ada fluktuasi tapi saya pikir (4/3) 2 ^ k adalah kasus terburuk dan lebih baik untuk kasus lain.

David Eppstein

Penyortiran perbandingan acak optimal

Jawaban: