Apa yang lebih sulit: Mengocok dek yang diurutkan atau mengurutkan yang dikocok?

18

Anda memiliki larik elemen yang berbeda. Anda memiliki akses ke pembanding (fungsi kotak hitam mengambil dua elemen dan dan mengembalikan true iff ) dan sumber bit yang benar-benar acak (fungsi kotak hitam tidak mengambil argumen dan mengembalikan bit acak yang seragam secara independen). Pertimbangkan dua tugas berikut:naba<b

  1. Array saat ini diurutkan. Menghasilkan permutasi yang seragam (atau kurang lebih seragam) secara acak.
  2. Array terdiri dari beberapa permutasi yang dipilih secara seragam secara acak. Menghasilkan array yang diurutkan.

Pertanyaanku adalah

Tugas mana yang membutuhkan lebih banyak energi tanpa gejala?

Saya tidak dapat mendefinisikan pertanyaan lebih tepat karena saya tidak cukup tahu tentang hubungan antara teori informasi, termodinamika, atau apa pun yang diperlukan untuk menjawab pertanyaan ini. Namun, saya pikir pertanyaannya dapat dibuat dengan jelas (dan saya berharap seseorang membantu saya dengan jawaban ini!).

Sekarang, secara algoritmik, intuisi saya adalah mereka setara. Perhatikan bahwa setiap jenis adalah acak secara terbalik, dan sebaliknya. Penyortiran membutuhkan perbandingan, sambil mengocok, karena mengambil permutasi acak daripilihan, membutuhkan bit acak. Pengocokan dan penyortiran membutuhkan sekitar swap.log⁡n!≈nlog⁡nn!log⁡n!≈nlog⁡nn

Namun, saya merasa harus ada jawaban yang menerapkan prinsip Landauer , yang mengatakan bahwa itu memerlukan energi untuk "menghapus" sedikit. Secara intuitif, saya pikir ini berarti bahwa menyortir array lebih sulit, karena memerlukan "menghapus" bit informasi, beralih dari keadaan gangguan energi rendah, entropi tinggi ke gangguan yang sangat teratur. Tetapi di sisi lain, untuk setiap perhitungan yang diberikan, penyortiran hanya mengubah satu permutasi ke yang lain. Karena saya benar-benar non-ahli di sini, saya berharap seseorang dengan pengetahuan tentang koneksi ke fisika dapat membantu "menyelesaikan" ini!nlog⁡n

(Pertanyaannya tidak mendapatkan jawaban pada math.se , jadi saya memposting ulang di sini. Semoga tidak apa-apa.)

algorithms algorithm-analysis information-theory permutations entropy usul
sumber
Saya belum memikirkan ini sama sekali, jadi peringatan lector. Jika kita mulai dengan array yang diurutkan, maka gunakan sortir gabungan, tetapi alih-alih membandingkan, kita menggunakan bit acak untuk melakukan penggabungan (jadi alih-alih mengembalikan true iff kita mengembalikan true iff bit acak adalah 1 ). Kasus dasar di mana kita memiliki dua larik ukuran satu menghasilkan dua larik kemungkinan ukuran dua dengan probabilitas yang seragam. Saya belum melangkah lebih jauh dari itu. Sebuah<b1
Luke Mathies
2
Saya pikir untuk menjawab pertanyaan ini, pertama-tama Anda perlu menentukan biaya relatif operasi; berapa biayanya untuk membaca data, menulis data, dan menghasilkan / memperoleh nomor acak?
mitchus
@itchus: Saya terutama ingin tahu tentang batas fisik jika kita menganggap komputer "efisien secara optimal". Pemahaman kasar saya adalah bahwa ada batas fisik yang lebih rendah pada jumlah energi yang diperlukan untuk "menghapus" sedikit informasi, sementara operasi lain membutuhkan energi yang jauh lebih sedikit. Jadi saya bertanya-tanya apakah intuisi ini benar dan cukup dapat diformalkan untuk menghasilkan jawaban.
usul
Apa yang Anda maksud dengan menghapus sedikit? Timpa itu? Sejauh yang saya tahu komputer biasanya tidak menghapus apa pun (kecuali untuk alasan privasi) tetapi hanya "lupa" dengan de-alokasi wilayah memori yang terkait. Tapi mungkin saya tidak memahami level abstraksi dengan benar di sini :)
mitchus
2
@ Patrick87 Sayangnya, model energi yang seragam terlalu jauh dari kebenaran untuk menggunakannya; lihat Mengevaluasi Algoritma berdasarkan Konsumsi Energi mereka oleh Fudeus née Bayer dan Nebel (2009).
Raphael

Jawaban:

6

nlogn!≈nlog2⁡n(nln⁡n)kTnlog2⁡n

Perhatikan bahwa ini hanyalah batas bawah teoretis. Energi yang saat ini dikonsumsi oleh proses-proses ini pada komputer digital yang sebenarnya tidak ada kaitannya dengan analisis di atas.

Peter Shor
sumber
Terima kasih banyak! Bisakah saya meminta tindak lanjut yang naif? Misalkan saya mengubah kata-kata dari pertanyaan sehingga algoritma pengurutan diberi beberapa permutasi tetap dari item dan harus mengurutkannya. Sekarang, jika Anda berlangganan filosofi Bayesian dan memiliki kepercayaan seragam pada masukan ini, tampaknya jawabannya harus sama. Tetapi di bawah filosofi bahwa tidak ada keacakan dalam input (walaupun saya tidak tahu apa itu), argumen tersebut tampaknya gagal. Bagaimana saya menyelesaikan paradoks? Terima kasih lagi!!
usul
(nln⁡n)kT
3

Tidak juga. Setiap sirkuit dapat dibuat reversibel dengan melacak input, dan disipasi energi dari perhitungan reversibel dapat dibuat kecil sewenang-wenang .

rphv
sumber
tetapi membuatnya reversibel mungkin membuatnya tidak efisien. Apa hubungan antara algoritma optimal . BTW, saya tidak berpikir mereka membandingkan. Mengocok secara inheren membutuhkan keacakan (dan keacakan yang berbeda akan menghasilkan keluaran yang berbeda). Penyortiran mungkin bersifat deterministik. Penyortiran "Reversing" akan bergerak secara deterministik
Ran G.
1
Dengan "efisien", maksud Anda adalah waktu, ruang, atau kombinasi keduanya? Membuat perhitungan reversibel tidak selalu menambah kompleksitas waktu asimptotik, dan ada versi reversibel dari setiap perhitungan yang tidak menggunakan lebih banyak ruang daripada yang asli [Vitányi05] .
rphv
1
Selama Anda menyimpan input, sirkuit apa pun dapat dibuat reversibel. Jika Anda tidak ingin menyimpan informasi yang dapat merekonstruksi permutasi asli, sirkuit penyortiran tidak dapat dibuat reversibel.
Peter Shor