Elemen perbedaan dalam O (n) waktu?

Kita semua tahu bahwa perbedaan elemen dalam model berbasis perbandingan tidak dapat dilakukan dalam waktu . Namun, pada RAM kata, seseorang mungkin dapat mencapai yang lebih baik.$o(n\log n)$

Tentu saja, jika kita mengasumsikan adanya fungsi hash sempurna yang dapat dihitung dalam waktu linier, kita mendapatkan algoritma waktu linier untuk perbedaan elemen: tetap saja hashing angka satu per satu dan kembalikan 1 jika ada tabrakan.

Namun, ada dua masalah: 1) sebagian besar konstruksi fungsi hash sempurna yang saya dapat menemukan keacakan digunakan dan 2) Saya tidak dapat menemukan diskusi tentang waktu pra-pemrosesan di mana saja, yaitu, waktu yang diperlukan untuk memutuskan fungsi hash mana yang sedang berjalan untuk digunakan berdasarkan set input angka.

Fredman et al. " Menyimpan tabel jarang dengan waktu akses kasus terburuk$O(1)$ O ( 1 ) " tidak menyelesaikan masalah pertama dengan menyediakan fungsi hash dengan waktu akses dalam kasus terburuk, tetapi tidak mengatakan apa pun tentang masalah kedua .$O(1)$

Singkatnya, inilah yang saya inginkan:

Merancang sebuah algoritma yang diberikan satu set dari angka (masing-masing nomor yang bit panjang) pada kata-RAM dengan panjang kata , menemukan fungsi hash di waktu, di mana . Fungsi harus memiliki properti yang untuk setiap , jumlah elemen yang dipetakan ke adalah konstan dan menghitung harus mengambiln w w h : S → { 1 , ... , m } O ( n ) m = O ( n ) h j ∈ { 1 , ... , m } S j h ( i ) O ( 1 $S$$n$$w$$w$$h:S\rightarrow \{1, \ldots , m\}$$O(n)$$m = O(n)$$h$$j \in \{1, \ldots , m\}$$S$$j$$h(i)$$O(1)$waktu dalam model kata-RAM "masuk akal", yaitu, model tidak boleh membiarkan fungsi "eksotis" pada kata-kata dievaluasi dalam waktu .$O(1)$

Saya juga ingin tahu apakah ada algoritma untuk menyelesaikan elemen yang berbeda pada kata-RAM yang tidak menggunakan fungsi hash sama sekali.

Perbedaan elemen dapat dipecahkan secara deterministik dalam model RAM dalam waktu dalam :$O(n\log\log n)\subset o(n\log n)$

Urutkan waktu dalam Anda jumlah bit menggunakan algoritma sorting dijelaskan oleh Han di stoc 2002 ( "deterministik menyortir di waktu dan ruang linear"), kemudian memindai dalam waktu linier untuk tabrakan.n w O ( n log log n $O(n\log\log n)$$n$$w$$O(n\log\log n)$

Sejauh yang saya tahu, itulah hasil terbaik yang diketahui sampai hari ini.

Itulah yang dilakukan oleh makalah FKS yang Anda sebutkan - dan ini membutuhkan waktu linier (dengan harapan). Lihat halaman 5 di sini untuk analisis ... http://www1.icsi.berkeley.edu/~luby/PAPERS/pairwise.ps