Penyortiran perbandingan acak optimal

12

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 n = 4 , batas bawah deterministik adalah lima perbandingan, tetapi algoritma acak (permutasi acak input dan kemudian menerapkan jenis gabungan) tidak lebih baik, memiliki 4 2log2n!n=4 perbandingan untuk semua input.423

The terikat tanpa langit-langit masih berlaku dalam kasus acak, dengan argumen informasi-teoretis, dan dapat sedikit diperketat menjadi k + 2 ( n ! - 2 k )log2n! 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+2(n!2k)n!, where k=log2n!.

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 n ! Tidak pernah merupakan kekuatan dua) . Tetapi seberapa jauh lebih baik?n>2n!

David Eppstein
sumber
lg(n!)+o(n)

Jawaban:

4

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

http://arxiv.org/abs/1307.3033

logn!+cnc

Pat Morin
sumber
nlogn1.415nnlogn1.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