Wybierz dwie liczby, które sumują się do , używając sublinearnego czasu zapytania

9

Oto problem najbliższego sąsiada.

Biorąc pod uwagę liczby rzeczywiste (bardzo duże !), Plus cel rzeczywisty , znajdź i których SUMA jest najbliższe . Umożliwiamy rozsądne wstępne przetwarzanie / indeksowanie (do ), ale w czasie zapytania (dane ) wynik powinien zostać zwrócony bardzo szybko (np. czas). $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)$

(Prostszy przykład: jeśli chcielibyśmy tylko POJEDYNCZEGO najbliższego , posortowalibyśmy offline, , a następnie przeszukaliśmy binarnie w czasie zapytania, ). $a_i$ $p$ $a_1, \ldots, a_n$ $O(n \log n)$ $O(\log n)$

Rozwiązania, które nie działają:

1) Sortuj offline, a następnie w czasie zapytania zacznij od obu końców i przesuń dwa wskaźniki do wewnątrz ( http://bit.ly/1eKHHDy ). Nie dobrze, ze względu na czas zapytania . $a_1, \ldots, a_n$ $O(n)$

2) Posortuj offline, a następnie w czasie zapytania, weź każdy i przeprowadź wyszukiwanie binarne dla „kumpla”, który pomoże sumować się do czegoś zbliżonego do . Nie dobrze, ze względu na czas zapytania . $a_1, \ldots, a_n$ $a_i$ $p$ $O(n \log n)$

3) Posortuj wszystkie pary offline, a następnie przeprowadź wyszukiwanie binarne. Nie dobrze, ze względu na wstępne przetwarzanie . $(a_{1}, \ldots, a_{n})$ $O(n^2)$

Dzięki!

ps. Do uogólnienia potrzebne są dalsze uogólnienia: (1) i to wektory 50-wymiarowe, (2) „close” oznacza wektorową odległość cosinus i (3) najbliższe pary-suma, nie tylko 1 najlepszy. $a_1, \ldots, a_n$ $p$ $k$

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

— Kevin
źródło

Czy istnieje limit czasu przetwarzania wstępnego lub ilości miejsca, które możemy wykorzystać po przetwarzaniu wstępnym? Jeśli ograniczamy się do przestrzeni , czy masz powód, by sądzić, że można ją rozwiązać na przykład w czasie ? To wydaje mi się strasznie mało prawdopodobne.

O (n)

$O(n)$

O (\lg n)

$O(\lg n)$

— DW

Przetwarzanie wstępne jest ograniczone do O ( log ). Zaktualizowałem opis problemu.

n

$n$

n

$n$

— Kevin,

Nie mam żadnego powodu, aby sądzić, że zapytania mogą być szybkie, ale wiele przydatnych wyników dla najbliższych sąsiadów (drzewa kd, haszowanie wrażliwe na lokalizację itp.) Wydaje mi się sprzeczne z intuicją. Przydatne byłoby zastosowanie przybliżonego rozwiązania wykorzystującego haszowanie wrażliwe na lokalizację.

— Kevin,

17

Jest to prawie na pewno niemożliwe.

Załóżmy, że możesz rozwiązać problem z czasem wstępnego przetwarzania i czasem zapytania . Następnie istnieje prosty algorytm do rozwiązania problemu 3SUMA - biorąc pod uwagę zestaw liczb rzeczywistych, czy jakieś trzy elementy sumują się do zera? - w czasie . Wstępnie przetwarzamy wszystkie liczby, a następnie dla każdej liczby znajdujemy wartość najbliższą ; jeśli dokładnie pasuje do , znaleźliśmy rozwiązanie problemu 3SUM. $P(n)$ $Q(n)$ $n$ $P(n)+n\cdot Q(n)$ $a_k$ $a_i+a_j$ $-a_k$ $-a_k$

Jednak najszybszy znany algorytm dla 3SUM działa w czasie i ten algorytm jest powszechnie przypuszczany, że jest optymalny. Ponadto istnieje dopasowana dolna granica w ograniczonym, ale naturalnym modelu obliczeń drzewa decyzyjnego. W przypadku zestawów całkowitymi , są nieco algorytmy subquadratic, że „czas grać w gry z bitów”, ale także w modelach RAM całkowitą, 3SUM Przypuszcza wymagają Czas . $O(n^2)$ $\Omega(n^2)$ $\Omega(n^2/\text{polylog}\,n)$

Zakładając, że przypuszczenie jest poprawne, twój problem albo wymaga (prawie) kwadratowego czasu wstępnego przetwarzania, albo (prawie) liniowego czasu zapytania.

— Jeffε
źródło

2

Jeśli podczas wstępnego przetwarzania można użyć nieograniczonej przestrzeni i nieograniczonego czasu, następujące rozwiązanie spełnia Twoje wymagania:

Podczas przetwarzania wstępnego oblicz zestaw i zapisz ten zestaw w posortowanej kolejności. Zestaw ten można wygenerować i posortować w czasie , a przechowywanie go zajmuje miejsce . $\{a_i+a_j:1\le i\le j\le n\}$ $O(n^2)$ $O(n^2)$
Teraz, aby odpowiedzieć na zapytanie (aby znaleźć gdzie jest tak blisko jak to możliwe), po prostu wykonaj wyszukiwanie binarne na tej posortowanej liście. To zajmie czas. $a_i,a_j$ $a_i+a_j$ $p$ $O(\lg n)$

Jeśli to rozwiązanie jest nie do przyjęcia, musisz dokładnie przemyśleć swoje wymagania i odpowiednio zmodyfikować pytanie.

— DW
źródło

Cześć i dziękuję! Ale twoje rozwiązanie jest takie samo jak moje rozwiązanie nr 3, które jest problematyczne z powodu czasu wstępnego przetwarzania O (n ^ 2). W moim przypadku n jest bardzo duże (np. 1 m) i muszę unikać operacji O (n ^ 2).

— Kevin,