Uogólniony problem z 3SUM (k-SUM)?

W 3SUM problemów próbuje zidentyfikować 3 liczb całkowitych z zestawu wielkości takie, że .S n a + b + c = $a,b,c$$S$$n$$a + b + c = 0$

Przypuszcza się, że nie ma lepszego rozwiązania niż kwadratowe, tj. . Lub inaczej: .o ( n log ( n ) + n 2$\mathcal{o}(n^2)$$\mathcal{o}(n \log(n) + n^2)$

Zastanawiałem się więc, czy dotyczy to uogólnionego problemu: Znajdź liczby całkowite dla w zestawie o rozmiarze takim, że . i ∈ [ 1 .. k ] S n ∑ i ∈ [ 1 .. k ] a i = $a_i$$i \in [1..k]$$S$$n$$\sum_{i \in [1..k]} a_i = 0$

Myślę, że możesz to zrobić w dla (generalizacja prostego algorytmu jest banalna . Ale czy są lepsze algorytmy dla innych wartości ?$\mathcal{o}(n \log(n) + n^{k-1})$$k \geq 2$$k=3$
$k$

$k$ SUMA można rozwiązać szybciej w następujący sposób.

• Dla parzystego :$k$ Oblicz posortowaną listę wszystkich sum elementów wejściowych . Sprawdź, czy S zawiera zarówno pewną liczbę x, jak i jej negację -x . Algorytm działa w czasie O (n ^ {k / 2} \ log n) .$S$$k/2$$S$$x$$-x$$O(n^{k/2}\log n)$

• Dla nieparzystego $k$ : oblicz posortowaną listę $S$ wszystkich sum $(k-1)/2$ elementów wejściowych. Dla każdego elementu wejściowego $a$ sprawdź, czy $S$ zawiera zarówno $x$ jak i $-a-x$ , dla pewnej liczby $x$ . (Drugi krok to zasadniczo algorytm czasu $O(n^2)$ dla 3SUM.) Algorytm działa w czasie $O(n^{(k+1)/2})$ .

Oba algorytmy są optymalne (z wyjątkiem ewentualnie współczynnika log, gdy $k$ jest parzyste i większe niż $2$ ) dla dowolnej stałej $k$ w pewnym słabym, ale naturalnym ograniczeniu modelu obliczeń liniowego drzewa decyzyjnego. Aby uzyskać więcej informacji, zobacz:

• Nir Ailon i Bernard Chazelle. Dolne granice dla testów liniowej degeneracji . JACM 2005.

• Jeff Erickson. Dolne granice dla problemów liniowej satysfakcji . CJTCS 1999.

-SUMA wymaga czasu n Ω ( d ), chyba że k-SAT można rozwiązać w czasie 2 o ( n ) dla dowolnej stałej k. Zostało to pokazane wartykuleMihai Patrascu i Ryana Williamsa (1).$d$$n^{\Omega(d)}$$2^{o(n)}$

Innymi słowy, przy założeniu wykładniczej hipotezy czasowej , algorytm jest optymalny aż do stałego współczynnika wykładniczego (współczynnik wielomianowy w )$n$

(1) Mihai Patrascu i Ryan Williams. O możliwości szybszych algorytmów SAT. Proc. 21. Sympozjum ACM / SIAM na temat algorytmów dyskretnych (SODA2010)

Oto kilka prostych spostrzeżeń.

Dla możesz to zrobić w czasie Θ ( n ) , skanując tablicę w poszukiwaniu zera. Dla k = 2 możesz to zrobić bez mieszania w czasie Θ ( n log n ) . Posortuj tablicę, a następnie zeskanuj ją. Dla każdego elementu szukam binarnie - i . Powoduje to całkowitą złożoność Θ ( n log n ) . W przypadku k = n możesz to zrobić w Θ ( n $k=1$$\Theta(n)$$k=2$$\Theta(n \log n)$$i$$-i$$\Theta(n \log n)$$k=n$$\Theta(n)$ czas, kumulując tablicę i sprawdzając wynik.

Aby uzyskać więcej informacji, zobacz stronę The Open Problems Project dla 3SUM .

Zobacz http://arxiv.org/abs/1407.4640

Nowy algorytm rozwiązywania problemu rSUM Valerii Sopin

Abstrakcyjny:

Przedstawiony jest określony algorytm rozwiązywania problemu rSUM dla dowolnego naturalnego rz subkwadratową oceną złożoności czasowej w niektórych przypadkach. Pod względem ilości użytej pamięci uzyskany algorytm ma również porządek subkwadratowy. Idea uzyskanego algorytmu oparta jest nie na liczbach całkowitych, lecz na k∈N kolejnych bitach tych liczb w systemie numeracji binarnej. Pokazano, że jeśli suma liczb całkowitych jest równa zero, to suma liczb prezentowanych przez dowolne k kolejnych bitów tych liczb musi być wystarczająco „bliska” zeru. Umożliwia to odrzucenie liczb, które tym bardziej nie ustalają rozwiązania.

To coś nowego w tym numerze.