Apakah penyortiran bilangan bulat dimungkinkan dalam O (n) dalam model transdichotomous?

Setahu saya tidak ada algoritma kasus terburuk yang memecahkan masalah berikut: $O(n)$

Dengan urutan panjang terdiri dari bilangan bulat terbatas, temukan permutasi di mana setiap elemen kurang dari atau sama dengan penggantinya. $n$

Tetapi apakah ada bukti bahwa itu tidak ada, dalam model komputasi transdichotomous ?

Perhatikan bahwa saya tidak membatasi rentang bilangan bulat. Saya juga tidak membatasi solusi untuk jenis perbandingan.

complexity-theory sorting computation-models lower-bounds orlp
sumber

Sejauh yang saya tahu, mungkin ada algoritma waktu untuk SAT! Jadi jawabannya tidak.

O (n)

$O(n)$

Lembik

AFAIK, ini masih merupakan masalah terbuka.

Juho

Saya tidak tahu apakah ada jawaban yang bermakna sampai Anda menentukan model perhitungan apa yang Anda gunakan, mengingat Anda tidak membatasi komputer Anda untuk melakukan perbandingan dan pertukaran. Dengan hanya RAM dan perbandingan dua angka, argumen dari entropi memberikan batas waktu , bahkan untuk komputer transdichotomous. Secara sepele, jika alih-alih swap dan perbandingan, penyortiran adalah operasi dasar, itu dapat dilakukan dalam . Jika memasukkan bilangan bulat di tempat yang tepat adalah operasi elementer, . Apakah Anda memiliki model spesifik di luar perbandingan-swap?

Ω (n \cdot l o g (n))

$\Omega(n\cdot log(n))$

Θ (1)

$\Theta(1)$

Θ (n)

$\Theta(n)$

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen Pertanyaan saya menentukan model komputasi transdichotomous. Dalam bahasa Inggris biasa: model perhitungan di mana ukuran kata mesin cukup besar untuk menampung bilangan bulat masalah apa pun. Jadi membandingkan dua bilangan bulat adalah O (1), tetapi demikian juga menambahkan, mengalikan, dll. Dalam model perhitungan ini, ikatan entropik telah dipukuli, lihat Han, Yijie (2004), "Penyortiran deterministik dalam O (n log log n) waktu dan ruang linear" .

orlp

@ Atau saya melihat; jika Anda mengambil keuntungan dari struktur bilangan bulat, Anda dapat mengalahkan ikatan entropis. Saya tidak tahu tentang penyortiran bilangan bulat; Saya pasti akan membaca tentang topik itu!

Lieuwe Vinkhuijzen

Jawaban:

Integer dapat diurutkan secara stabil dalam waktu dengan ruang tambahan. $O(n)$ $O(1)$ Lebih tepatnya, jika Anda memiliki bilangan bulat dalam kisaran , dapat diurutkan dalam waktu O (n). $n$ $[1, n^c]$

Ini hanya ditunjukkan beberapa tahun yang lalu oleh sebuah tim termasuk almarhum Mihai Pătrașcu (yang seharusnya mengejutkan siapa pun yang akrab dengan pekerjaannya). Ini adalah hasil yang luar biasa yang saya terkejut lebih banyak orang tidak tahu, karena itu berarti masalah penyortiran bilangan bulat (secara teoritis) diselesaikan.

Ada algoritma praktis (diberikan dalam makalah di atas) jika Anda diizinkan untuk memodifikasi kunci. Pada dasarnya, Anda dapat mengompresi bilangan bulat yang disortir lebih banyak daripada Anda dapat mengompresi bilangan bulat yang tidak disortir, dan ruang ekstra yang Anda peroleh persis sama dengan memori tambahan yang diperlukan untuk melakukan pengurutan radix. Mereka juga memberikan algoritma yang tidak praktis yang mendukung kunci read-only.

Nama samaran
sumber

Dari apa yang saya mengerti dari abstrak ini tidak umum - hanya dapat mengurutkan kata hingga dalam ukuran . Pertanyaan saya secara eksplisit menyebutkan bilangan bulat tanpa batas.

\log n

$\log n$

O (n)

$O(n)$

orlp

@orlp Algoritma ketiga dalam makalah ini berbicara tentang bilangan bulat tanpa batas.

Nama samaran

Mungkin saya salah membaca, tapi saya hanya bisa melihat deskripsi metode untuk mengurangi penggunaan memori dari algoritma pengurutan integer tak terbatas. Mengutip dari abstrak (penekanan): "Pertanyaan lain yang menarik adalah kasus sewenang-wenang Berikut ini kami sajikan transformasi kotak hitam dari setiap RAM algoritma sorting untuk algoritma sorting yang hanya menggunakan O (1) ruang ekstra dan memiliki. Sama waktu berjalan . " $c$

orlp

Maafkan saya, tetapi dalam kondisi saat ini, jawaban ini tidak menjawab pertanyaan sama sekali . Saya secara eksplisit menyebutkan bahwa bilangan bulat tidak dibatasi . Jawaban ini memecahkan masalah yang sama sekali berbeda.

orlp

Poin terakhir sekarang tidak lagi dalam font kecil :)

orlp

-1

$O(bn)$ $b$ $n$

Jika tidak ada batas atas pada ukuran bilangan bulat Anda, maka saya tidak percaya ada algoritma penyortiran waktu-dikenal.

RFC 2549
sumber

Selamat datang! Apa yang Anda katakan sepenuhnya benar tetapi saya tidak berpikir itu menjawab pertanyaan. Pertanyaannya menanyakan secara spesifik bukti bahwa algoritma yang diperlukan tidak ada dalam model komputasi tertentu; hanya mengatakan bahwa tidak ada algoritma yang diketahui tidak membuktikan tidak ada.

David Richerby

Sebenarnya, b menjadi konstan dalam masalah kami, saya menganggap algoritma ini berada di o (n)

RFC 2549

b

$b$

n

$n$

O (n)

$O(n)$

o (n)

$o(n)$

Ya, pasti salah ketik;) dalam pertanyaannya, karena Anda mengira angka cocok dengan panjang kata b, itu menjadi konstan.

RFC 2549

Itu tidak membuat panjang kata konstan. (Jika tidak, tidak akan ada alasan untuk secara eksplisit menganggap "bahwa operasi pada kata-kata tunggal mengambil waktu konstan per operasi".