Kompleksitas semacam buta?

Kita semua tahu bahwa kompleksitas minimal dari algoritma pengurutan berbasis perbandingan adalah perbandingan . Saya mencoba untuk melakukan semacam buta , yaitu diberi nomor keluaran sirkuit (dengan gerbang boolean, aritmatika dan "perbandingan") yang mengurutkan daftar item . $\Omega(n \log n)$ $n$ $n$

Mempersiapkan semua perbandingan ${n \choose 2}$ dan kemudian melakukan aritmatika pada bit yang dihasilkan membuat saya algoritma $\Theta(n^3)$ , namun oleh beberapa "pointer aritmatika" gila, saya pikir saya bisa mendapatkan $\Theta(n^2)$ Versi: kapan.

Apakah ada batas bawah yang diketahui untuk sirkuit pemilahan berbasis perbandingan sepanjang garis yang mirip dengan $n \log n$ satu untuk algoritma pemilahan berbasis perbandingan? Mungkinkah menutup mata untuk mengurutkan waktu $n \log n$ ?

cc.complexity-theory terminology sorting Bristol
sumber

Apa latar belakangmu? Apakah Anda mencari di sekitarnya? mis. penyortir bionik memberikan jaringan yang baik dengan ukuran

O (n \cdot \log^{2} n)

$O(n\cdot {\log^2 n})$ , dan waktu untuk membuat jaringan yang sesuai paling besar sebagai ukuran jaringan.

Saeed

Latar belakang saya adalah dalam kriptografi dan saya sedang memilah-milah data rahasia yang dibagi, yang memberikan beberapa kendala yang agak tidak biasa pada biaya relatif operasi. Saya bertanya-tanya apakah saya telah mencapai kasus tepi di mana n^2batas bawah atau apakah itu tidak dapat dibawa ke yang biasa n log nsetelah semua - hanya memeriksa untuk melihat apakah ada situasi di mana batas yang lebih tinggi seperti n^2yang sudah diketahui.

Bristol

Sebenarnya berdasarkan latar belakang yang saya maksudkan, karena di sini orang mencoba untuk mengajukan pertanyaan tingkat penelitian , jadi ketika Anda memberikan pendekatan yang sangat naif berarti tidak ada banyak penelitian di balik pertanyaan itu, mungkin beberapa situs lain lebih cocok untuk ini.

Saeed

Saya pikir istilah teknis untuk apa yang Anda sebut penyortiran buta tidak disadari " jaringan penyortiran " .

Kaveh

Kompleksitas semacam buta?

Jawaban: