Struktur data berbasis perbandingan untuk menemukan item

Apakah ada struktur data yang mengambil array yang tidak berurutan dari item, melakukan preprocessing di dan menjawab pertanyaan: apakah ada beberapa elemen dalam daftar, setiap query dalam waktu terburuk ? $n$ $O(n)$ $x$ $O(\log n)$

Saya benar-benar berpikir tidak ada, jadi bukti bahwa tidak ada juga disambut.

ds.data-structures sorting Chi-Lan
sumber

(1) Saya tidak tahu mengapa Anda bisa mengatakan "Tentu saja saya mempertimbangkan waktu yang diharapkan," karena Anda tidak menyatakan "diharapkan" dalam pertanyaan Anda sama sekali. Silakan coba untuk menyatakan pertanyaan Anda lebih tepatnya sebelum berkata (2) silakan mendefinisikan “tentu saja.” “Non-hashable.”

Tsuyoshi Ito

(1) Begitu. Terima kasih untuk penjelasannya. Jika seseorang bertanya "Apakah Anda peduli dengan waktu berjalan?" Maka jawabannya akan memang "tentu saja." :) (2) Saya pikir bahwa "Satu-satunya tindakan yang diizinkan adalah membandingkan dua nilai dalam daftar" jauh lebih tepat dari sekadar menyatakan "tidak hash." Bisakah Anda mengedit pertanyaan sehingga orang tidak perlu membaca komentar untuk memahami apa yang dimaksud "tidak hash"?

Tsuyoshi Ito

Omong-omong, jika Anda tidak dapat membuktikannya, mengapa Anda tahu itu tidak mungkin? Jika ini adalah latihan di buku teks atau kelas, Anda bertanya di situs web yang salah.

Tsuyoshi Ito

Apakah ini pertanyaan Anda: Apakah ada struktur data yang mengambil array yang tidak berurutan dari n item, melakukan preprocessing dalam O (n) dan menjawab pertanyaan: apakah ada beberapa elemen x dalam daftar, setiap kueri dalam waktu terburuk O (log n)?

sdcvvc

@Filip: Apakah mudah dilihat? Jika itu benar, maka saya setuju bahwa itu menyelesaikan pertanyaan.

Tsuyoshi Ito

Jawaban:

Ini bukti bahwa itu tidak mungkin. Misalkan Anda dapat membangun struktur data seperti itu. Bangun itu. Kemudian pilih item secara acak dari daftar, tambahkan ke masing-masing, di mana lebih kecil dari perbedaan antara dua item dalam daftar, dan lakukan kueri untuk memeriksa apakah ada item yang dihasilkan di dalam daftar. Anda telah melakukan pertanyaan sejauh ini. $n/\log n$ $\epsilon$ $\epsilon$ $O(n)$

Saya ingin mengklaim bahwa perbandingan yang telah Anda lakukan cukup untuk mengetahui apakah item pada daftar asli lebih kecil dari atau lebih besar dari item baru . Misalkan Anda tidak tahu. Kemudian, karena ini adalah model berbasis perbandingan, Anda tidak akan tahu apakah sama dengan atau tidak, sebuah kontradiksi dari asumsi bahwa struktur data Anda berfungsi. $a$ $b$ $a$ $b$

Sekarang, karena item yang Anda pilih adalah acak, perbandingan Anda dengan probabilitas tinggi diberikan informasi yang cukup untuk membagi daftar asli menjadi daftar masing-masing ukuran . Dengan mengurutkan masing-masing daftar ini, Anda mendapatkan algoritma pengurutan waktu secara acak hanya berdasarkan perbandingan, suatu kontradiksi. $n/\log n$ $n/\log n$ $O(\log n)$ $O(n \log \log n)$

Peter Shor
sumber

Beberapa petunjuk untuk membantu memahami bukti (dengan asumsi saya mengerti benar sendiri tentu saja): the

item harus diisi dengan barang-barang setelah

telah ditambahkan ke mereka; perbandingan model yang jaminan Anda tahu mana kasus

dan

memegang; yang

daftar berada di 'urutan menaik': setiap elemen dalam daftar yang lebih tinggi lebih tinggi dari setiap elemen dalam daftar yang lebih rendah; setelah pertanyaan awal Anda memiliki informasi yang cukup untuk membuat daftar di sekitar item yang Anda pilih secara acak,

b

$b$

ϵ

$\epsilon$

a \leq b

$a \leq b$

a \geq b

$a \geq b$

n / \log n

$n / \log n$

Alex ten Brink

(lanjutan) catat bahwa Anda bahkan tidak harus secara eksplisit dapat membuat daftar pada waktu yang disediakan untuk bukti yang dipegang.

Alex ten Brink

Saya tidak diam mengerti bukti ini. Kontradiksi terakhir adalah mematikan "algoritma yang hanya didasarkan pada perbandingan", tetapi pada langkah pertama dari algoritma kami, kami menambahkan

untuk setiap item (lebih lanjut, "di mana

lebih kecil daripada perbedaan antara dua item dalam daftar"). Mengapa kami masih dapat dibenarkan bahwa algoritme kami masih hanya berbasis perbandingan jika kami berasumsi bahwa barang kami memiliki total order non-diskrit?

ϵ

$\epsilon$

ϵ

$\epsilon$

Artem Kaznatcheev

@Artem: input asli Anda terdiri dari elemen

. Kemudian Anda membangun set baru

; Anda mewakili asli

sebagai

dan dimodifikasi

sebagai

. Sekarang Anda menggunakan algoritma kotak hitam; Algoritma membandingkan elemen-elemen

x \in X

$x \in X$

X^{'} = X \times {0, 1}

$X' = X \times \{0,1\}$

x \in X

$x \in X$

(x, 0) \in X^{'}

$(x,0) \in X'$

x + ϵ

$x + \epsilon$

(x, 1) \in X^{'}

$(x,1) \in X'$

X^{'}

$X'$ satu sama lain; untuk menjawab pertanyaan seperti itu, Anda hanya perlu membandingkan jumlah elemen

konstan satu sama lain. Karenanya semuanya harus dapat dilakukan dalam model perbandingan, dengan overhead konstan.

X

$X$

Jukka Suomela

@Aryabhata: ya. Apa itu algoritma

O (\log^{2} n)

$O(\log^2 n)$

Peter Shor

Saya percaya di sini adalah bukti yang berbeda, membuktikan ketidakmungkinan struktur waktu permintaan , dengan pra-pemrosesan. $\mathcal{O}(\log ^k n)$ $\mathcal{O}(n)$

Misalkan dalam preprocessing Anda melakukan perbandingan , yang mengarah ke urutan parsial. $\mathcal{O}(n)$

Sekarang pertimbangkan ukuran dari barang antik terbesar di dalamnya. Karena elemen-elemen ini tidak dapat dibandingkan, agar kita memiliki algoritma kueri , kita harus memiliki . $A$ $\mathcal{O}(\log ^k n)$ $A = \mathcal{O}(\log ^k n)$

Sekarang oleh teorema Dilworth, ada partisi ukuran , menjadi rantai. $A$

Sekarang kita bisa melengkapi algoritme untuk menentukan rantai di partisi. Kita dapat menentukan apakah dua elemen dapat dibandingkan dengan membuat grafik perbandingan yang diarahkan dan melakukan analisis keterjangkauan. Ini dapat dilakukan tanpa perbandingan tambahan. Sekarang cukup paksa keluar setiap kemungkinan partisi ukuran untuk menentukan apakah itu adalah partisi rantai. $A$

Setelah kami memiliki rantai, kami dapat menggabungkannya untuk memberikan algoritma perbandingan untuk mengurutkan seluruh daftar. $\mathcal{O}(n \log \log n)$

Aryabhata
sumber

Ini ide yang bagus. Dan jika Anda dapat menunjukkan bahwa partisi rantai harus diketahui oleh algoritme maka Anda dapat menggunakan mergesort untuk menunjukkan bahwa itu hanya akan mengambil perbandingan O (n log log n) tambahan untuk mengurutkan seluruh input, daripada menggunakan Jensen. Tetapi ada masalah: mengapa algoritma preprocessing harus membangun partisi rantai? Partisi rantai harus ada, ya, tapi itu sangat berbeda dari yang diketahui oleh algoritma.

David Eppstein

Ok, sekarang saya percaya bukti ini. Dan itu menunjukkan lebih kuat bahwa untuk mencapai waktu permintaan polylog Anda harus menggunakan sejumlah perbandingan yang ada dalam aditif

dari penyortiran. Bagus. Ngomong-ngomong, partisi rantai dapat ditemukan dalam waktu polinomial dari serangkaian perbandingan yang telah dilakukan, daripada membutuhkan pencarian kasar, tetapi itu tidak membuat perbedaan untuk argumen Anda.

O (n \log \log n)

$O(n\log\log n)$

David Eppstein

Bukti benar-benar menunjukkan bahwa Anda harus memiliki baik

preprocessing atau

untuk setiap query. Tentu saja keduanya ketat. Ini menunjukkan bahwa pencarian biner dan pencarian linear adalah satu-satunya algoritma pencarian "menarik" (setidaknya di dunia klasik).

Ω (n \log n)

$\Omega(n\log n)$

Ω (n)

$\Omega(n)$

Yuval Filmus

@Yuval: mungkin Anda harus menuliskan pengamatan ini sebagai jawaban yang sebenarnya, karena menurut saya Anda harus melakukan pekerjaan yang moderat untuk mendapatkan hasil di atas dari bukti dalam jawaban.

Peter Shor

@Yuval: memikirkan buktinya, saya hanya melihat bahwa Anda harus memiliki

preprocessing atau

waktu permintaan untuk semua

. Ini mungkin untuk memiliki

preprocessing waktu dan

waktu query. Satu dapat membagi daftar menjadi

daftar ukuran

masing-masing dalam waktu

Ω (n \log n)

$\Omega(n \log n)$

Ω (n^{1 - ϵ})

$\Omega(n^{1-\epsilon})$

ϵ

$\epsilon$

o (n \log n)

$o(n \log n)$

O (n / \log n)

$O(n / \log n)$

\log n

$\log n$

n / \log n

$n/\log n$

menggunakan penemuan median berulang.

θ (n \log \log n)

$\theta(n \log\log n)$

Peter Shor

Seperti yang dicatat oleh Peter Shor, untuk mengesampingkan keanggotaan dalam model berbasis perbandingan, kita perlu tahu bagaimana elemen tersebut dibandingkan dengan setiap anggota. Jadi, dengan menggunakan kueri acak (jumlah anggota lebih kecil dari kueri nonanggota adalah acak), kita memperoleh informasi relatif memiliki nilai yang tidak disortir. Oleh karena itu, untuk beberapa konstanta , menggunakan $k<n$ $Θ(n \log k)$ $n$ $c>0$ preprocesssing, kita tidak bisa memiliki $c \, n \log k$ permintaan biaya. Ini optimal hingga faktor konstan karena kita dapat mengurutkan data menjadi kira-kira sama ember (setiap ember tidak disortir) dalam waktu, yang memungkinkan biaya permintaan. $≤c \, n \log k/k$ $k' = k / \log k ≤ n/\log n$ $O(n \log k') = O(n \log k)$ $O(n/k')$

Secara khusus, menggunakan preprocessing, kami tidak dapat memiliki biaya permintaan. Juga, preprocessing sesuai dengan di untuk setiap dan dengan demikian biaya permintaan. $O(n)$ $o(n)$ $o(n \log n)$ $k$ $O(n^ε)$ $ε>0$ $Ω(n^{1−ε})$

Dmytro Taranovsky
sumber