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 2 perbandingan untuk semua input.
The terikat tanpa langit-langit masih berlaku dalam kasus acak, dengan argumen informasi-teoretis, dan dapat sedikit diperketat menjadi k + 2 ( n ! - 2 k ) 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.
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?
sumber
Jawaban:
Karena pertanyaan Anda adalah: "Apa yang diketahui?" Ini ada sesuatu:
http://arxiv.org/abs/1307.3033
sumber