Menggabungkan daftar objek yang rapuh

Latar belakang: Chao Xu memposting pertanyaan berikut beberapa waktu lalu: " Apakah ada algoritma penyortiran perbandingan yang diketahui tidak mengurangi untuk menyortir jaringan, sehingga setiap elemen dibandingkan dengan kali?$O(\log n)$ ". Tampaknya kita agak terjebak dengan masalah; Saya telah membahas masalah yang sama dengan Valentin Polishchuk pada tahun 2009, dan kami tidak berhasil.

Untuk mendapatkan ide-ide segar, saya mencoba untuk mengajukan pertanyaan paling sederhana yang memiliki cita rasa serupa dan tidak sepenuhnya sepele. Karena itu pertanyaan berikut.

Pertanyaan: Anda diberikan dua daftar yang diurutkan, masing-masing dengan elemen. Bisakah Anda menggabungkan daftar sehingga setiap elemen hanya dibandingkan kali?$n$$O(1)$

Secara alami, output harus berupa daftar yang diurutkan yang berisi semua elemen .$2n$

[Ini ternyata sepele, jawabannya adalah "tidak".]

Pertanyaan 2: Anda diberi dua daftar yang diurutkan, masing-masing dengan elemen. Bisakah Anda menggabungkan daftar sehingga setiap elemen hanya dibandingkan kali, jika Anda diizinkan untuk membuang sebagian kecil elemen ?$n$$O(1)$

Lebih tepatnya, output harus berupa daftar yang diurutkan yang berisi elemen , dan "trashcan" yang berisi elemen . Seberapa kecil Anda bisa membuat nilai ? Mendapatkan adalah sepele. Sesuatu seperti harus dapat dilakukan secara langsung. Tetapi bisakah Anda mendapatkan ?T ( n ) T ( n ) T ( n ) = n T ( n ) = n / 100 T ( n ) = o ( n $2n-T(n)$$T(n)$$T(n)$$T(n) = n$$T(n) = n/100$$T(n) = o(n)$

Catatan:

• Kami menggunakan model perbandingan di sini. Algoritme deterministik saja, kami tertarik pada jaminan kasus terburuk.

• Perhatikan bahwa kedua daftar memiliki elemen persis . Jika kita memiliki satu daftar dengan elemen dan satu lagi dengan elemen, jawabannya jelas "tidak"; namun, jika kedua daftar itu panjang, tampaknya orang mungkin dapat melakukan "load balancing".n $n$$n$$1$

• Kali ini segala jenis algoritma adalah valid. Jika algoritme Anda menggunakan jaringan sortir sebagai blok penyusun, itu baik-baik saja.

• Untuk titik awal, berikut adalah algoritma sederhana yang membandingkan setiap elemen paling banyak 200 kali: Cukup gunakan algoritma penggabungan standar, tetapi pertahankan counter untuk kepala daftar. Setelah Anda mencapai 200, buang elemen. Sekarang untuk setiap elemen yang Anda buang, Anda telah berhasil menempatkan 200 elemen dalam array output Anda. Karenanya Anda telah mencapai .$T(n) = n/100$

Tidak, algoritma seperti itu tidak bisa ada.

Asumsikan perbandingan per elemen diperbolehkan.$t$

$2^t$$2^t+1$$t+1$

$n$$n/2^t$$n/2^t$

$t$$o(n)$

Di samping catatan, tampaknya mungkin untuk mencocokkan ini terikat oleh suatu algoritma di mana setiap elemen dibandingkan dengan kira-kira log ukuran dari bagian sekitarnya dari daftar lainnya. Jika ini menarik, saya akan mencoba mencari tahu detailnya.