Kompleksitas Algoritma Shuffle Fisher-Yates

Pertanyaan ini berkaitan dengan algoritma Fisher-Yates untuk mengembalikan acak acak array yang diberikan. The halaman Wikipedia mengatakan bahwa kompleksitas adalah O (n), tapi saya berpikir bahwa itu adalah O (n log n).

Di setiap iterasi i, integer acak dipilih antara 1 dan i. Cukup menulis integer dalam memori adalah O (log i), dan karena ada iterasi, totalnya adalah

O (log 1) + O (log 2) + ... + O (log n) = O (n log n)

yang tidak lebih baik adalah algoritma naif. Apakah saya melewatkan sesuatu di sini?

Catatan: Algoritma naif adalah untuk menetapkan setiap elemen nomor acak dalam interval (0,1), lalu mengurutkan array terkait dengan nomor yang ditugaskan.

Saya menduga bahwa di sini, seperti dalam kebanyakan algoritme bekerja, biaya membaca dan menulis $O(\log n)$ angka bit diasumsikan konstan. Itu adalah dosa kecil, selama Anda tidak terbawa arus dan meruntuhkan P dan PSPACE secara tidak sengaja .

Model standar perhitungan mengasumsikan bahwa operasi aritmatika pada bilangan bulat O (log n) dapat dieksekusi dalam waktu yang konstan, karena operasi tersebut biasanya diserahkan pada perangkat keras. Jadi dalam algoritma Fisher-Yates, "menulis integer i dalam memori" hanya membutuhkan waktu O (1).

Tentu saja, itu sangat berarti untuk menganalisis algoritma dalam hal operasi bit, tetapi model biaya-bit kurang memprediksi perilaku aktual. Bahkan loop sederhana for i = 1 to n: print(i)membutuhkan operasi bit O (n log n).

Ini adalah jawaban untuk "[Algoritma Fisher-Yates] tidak lebih baik daripada algoritma naif. Apakah saya kehilangan sesuatu di sini?" yang Anda ajukan dalam pertanyaan.

Dalam algoritma "naif" Anda yang menggunakan bilangan real: berapa banyak bit akurasi yang Anda gunakan? Jika Anda menghitung kompleksitas bit (seperti yang tampaknya Anda lakukan untuk Fisher-Yates), dan algoritma ini menggunakan k bit acak untuk bilangan real, maka waktu berjalannya adalah Ω (kn log n), karena membandingkan dua k- bit angka real membutuhkan waktu Ω (k). Tetapi k harus setidaknya Ω (log n) untuk mencegah dua elemen dipetakan ke bilangan real yang sama, yang berarti bahwa algoritma tersebut mengambil Ω (n log ² n), yang lebih lambat dari pengocokan Fisher-Yates oleh faktor log n.

Jika Anda hanya menghitung jumlah operasi aritmatika dan perbandingan dan mengabaikan kompleksitas bitnya, maka Fisher-Yates adalah Θ (n) dan algoritme Anda adalah Θ (n log n), masih merupakan faktor log n yang terpisah.

Tidak ada yang istimewa tentang bilangan bulat untuk masalah ini.

Sebagai contoh, tabel hash (menyimpan segala jenis nilai) bukan O (1) waktu untuk mengakses jika fungsi hash harus membaca seluruh nilai untuk menghitung hash-nya. n elemen unik memerlukan log n bit masing-masing untuk direpresentasikan, tidak peduli seberapa pintar representasi Anda, dan fungsi hash apa pun yang membaca seluruh inputnya, oleh karena itu akan membutuhkan waktu paling sedikit untuk menghitung. Dalam praktiknya mereka lebih cepat daripada pohon merah-hitam, tetapi asimtotik mereka tidak lebih baik.

Brouhaha yang dirujuk oleh randomwalker adalah tentang makalah POPL 2008 ( http://portal.acm.org/citation.cfm?doid=1328438.1328460 ), dibahas di sini: http://blog.computationalcomplexity.org/2009/05/shaving- logs-with-unit-cost.html

Dalam posting itu Lance Fortnow menjelaskan bagaimana sebagai seorang siswa ia mengeluh bahwa menyortir benar-benar membutuhkan waktu n log ^ 2 n jika kita harus membaca semua log n bit dari dua elemen untuk membandingkan mereka, yang tampaknya keberatan yang masuk akal.

Halaman Wikipedia mengatakan bahwa kompleksitasnya adalah O (n), tetapi saya pikir itu adalah O (n log n).

Sebenarnya, O (n log n) adalah batas bawah untuk masalah ini dalam model di mana penyortiran adalah O (n log n). Jika semua permutasi memiliki kemungkinan yang sama maka algoritma sebagai fungsi dari aliran acak ke permutasi harus bersifat surjektif. Ada n! permutasi jadi dalam sesuatu seperti model pohon keputusan ada cabang panjang setidaknya O (log n!) = O (n log n).

Batas bawah kasus terburuk ini masih berfungsi untuk permutasi acak yang tidak seragam selama semua permutasi memiliki probabilitas yang tidak nol. Yang berubah adalah kompleksitas rata-rata. Sepertinya batas bawah pada kompleksitas rata-rata dalam model pohon keputusan adalah entropi distribusi. Dengan pohon keputusan biner, batas bawah ini hanya dapat dicapai dengan tepat ketika distribusinya bersifat diadik. Kasus ekstrem adalah ketika salah satu permutasi dibedakan memiliki probabilitas$1-\epsilon$dan yang lainnya memiliki probabilitas yang sama. Maka batas bawah pada kompleksitas rata-rata seharusnya$O(\epsilon)$.

Dalam TCS, kami mempertimbangkan - jika tidak dinyatakan secara eksplisit - kompleksitas pada Mesin Turing. Walaupun ini baik untuk tujuan teoretis, hasilnya tidak terlalu membantu dalam praktik karena kami menerapkan model mesin yang berbeda (yaitu, pendekatan terbatas) dalam perangkat keras. Oleh karena itu adalah pertanyaan yang layak untuk menanyakan kompleksitas pada model-model tersebut. Sebagai contoh, kami biasanya berasumsi bahwa mesin register (mirip dengan CPU nyata) dapat melakukan operasi atom pada dua register dalam waktu yang konstan - inilah yang mungkin telah digunakan di sini.

Singkatnya: Anda berpikir dalam hal TM, penulis artikel dalam hal RM. Anda berdua benar.