Pilih dua angka yang dijumlahkan ke , menggunakan waktu permintaan sub-linear

9

Ini masalah tetangga terdekat.

Diberikan real (sangat besar !), Plus target real , cari dan yang paling dekat dengan . Kami mengizinkan pra-pemrosesan / pengindeksan yang dari (hingga ), tetapi pada waktu kueri (diberikan ), hasilnya harus dikembalikan dengan sangat cepat (misalnya, waktu). $a_1, \ldots, a_n$ $n$ $p$ $a_i$ $a_j$ $p$ $a_1, \ldots, a_n$ $O(n \log n)$ $p$ $O(\log n)$

(Contoh sederhana: jika kita hanya menginginkan SINGLE yang paling dekat dengan , kita akan mengurutkan offline, , lalu melakukan pencarian biner pada waktu kueri, ). $a_i$ $p$ $a_1, \ldots, a_n$ $O(n \log n)$ $O(\log n)$

Solusi yang tidak berfungsi:

1) Urutkan offline, lalu pada waktu kueri, mulai dari kedua ujung & pindahkan dua pointer ke dalam ( http://bit.ly/1eKHHDy ). Tidak bagus, karena waktu permintaan. $a_1, \ldots, a_n$ $O(n)$

2) Urutkan offline, lalu pada waktu kueri, ambil setiap dan lakukan pencarian biner untuk "teman" yang membantunya menjumlahkan sesuatu yang dekat dengan . Tidak bagus, karena waktu kueri . $a_1, \ldots, a_n$ $a_i$ $p$ $O(n \log n)$

3) Urutkan semua pasangan offline, lalu lakukan pencarian biner. Tidak bagus, karena pra-pemrosesan. $(a_{1}, \ldots, a_{n})$ $O(n^2)$

Terima kasih!

ps. Diperlukan generalisasi lebih lanjut untuk latihan: (1) dan menjadi vektor 50-dimensi, (2) "tutup" menjadi jarak vektor kosinus, dan (3) -pasangan terdekat terdekat-jumlah itu, bukan hanya 1-terbaik. $a_1, \ldots, a_n$ $p$ $k$

ds.algorithms cg.comp-geom ds.data-structures Kevin
sumber

Apakah ada batasan waktu pra-pemrosesan atau jumlah ruang yang dapat kita gunakan setelah pra-pemrosesan? Jika kami terbatas pada ruang , apakah Anda memiliki alasan untuk meyakini bahwa itu dapat diselesaikan dalam, katakanlah, waktu? Bagi saya itu sangat tidak mungkin.

O (n)

$O(n)$

O (\lg n)

$O(\lg n)$

DW

Pra-pemrosesan terbatas pada O ( log ). Saya memperbarui pernyataan masalah.

n

$n$

n

$n$

Kevin

Saya tidak punya alasan untuk percaya bahwa query bisa cepat, tetapi banyak hasil yang berguna untuk tetangga terdekat (kd-tree, hashing yang sensitif terhadap lokalitas, dll.) Nampaknya kontra-intuitif baik untuk saya. Solusi perkiraan menggunakan hashing sensitif-lokal akan baik-baik saja untuk penggunaan praktis.

Kevin

17

Ini hampir pasti mustahil.

Misalkan Anda dapat memecahkan masalah Anda dengan waktu preprocessing dan waktu permintaan . Lalu ada algoritma sederhana untuk menyelesaikan masalah 3SUM — Berikan satu set bilangan real, apakah ada tiga elemen yang berjumlah nol? —Dalam waktu. Kami pra-proses semua angka, lalu untuk setiap angka , kami menemukan nilai yang paling dekat dengan ; jika cocok dengan , kami telah menemukan solusi untuk masalah 3SUM. $P(n)$ $Q(n)$ $n$ $P(n)+n\cdot Q(n)$ $a_k$ $a_i+a_j$ $-a_k$ $-a_k$

Namun, algoritma tercepat yang dikenal untuk 3SUM berjalan dalam waktu , dan algoritma ini secara luas diduga menjadi optimal. Selain itu, ada kecocokan batas bawah dalam model perhitungan pohon keputusan yang terbatas tetapi alami. Untuk set bilangan bulat , ada sedikit subquadratic-waktu algoritma yang "bermain game dengan bit", tetapi bahkan dalam model RAM integer, 3SUM ini menduga membutuhkan waktu . $O(n^2)$ $\Omega(n^2)$ $\Omega(n^2/\text{polylog}\,n)$

Jadi dengan asumsi dugaan itu benar, masalah Anda membutuhkan (dekat) waktu preprocessing kuadrat atau (dekat-) waktu permintaan linier.

Jeffε
sumber

2

Jika Anda dapat menggunakan ruang tak terbatas dan waktu tak terbatas selama pra-pemrosesan, maka solusi berikut ini memenuhi persyaratan Anda:

Selama pra-pemrosesan, hitung himpunan , dan simpan set ini dalam urutan yang diurutkan. Set ini dapat dibuat dan disortir dalam waktu , dan dibutuhkan ruang untuk menyimpannya. $\{a_i+a_j:1\le i\le j\le n\}$ $O(n^2)$ $O(n^2)$
Sekarang untuk menjawab pertanyaan (untuk menemukan di mana adalah sebagai dekat dengan mungkin), hanya melakukan pencarian biner dalam daftar diurutkan ini. Itu akan memakan waktu . $a_i,a_j$ $a_i+a_j$ $p$ $O(\lg n)$

Jika solusi ini tidak dapat diterima, Anda perlu memikirkan persyaratan Anda lebih hati-hati dan mengedit pertanyaan yang sesuai.

DW
sumber

Hai, dan terima kasih! Tetapi solusi Anda sama dengan solusi saya # 3, yang bermasalah karena waktu pra-pemrosesan O (n ^ 2). Dalam kasus saya, n sangat besar (misalnya, 1m) dan saya harus menghindari operasi O (n ^ 2).

Kevin

Pilih dua angka yang dijumlahkan ke , menggunakan waktu permintaan sub-linear

Jawaban: