Algorytm

Załóżmy, że podano różnych liczb całkowitych , takich, że dla pewnej stałej i dla wszystkich . $n$ $a_1, a_2, \dots, a_n$ $0 \le a_i \le kn$ $k \gt 0$ $i$

Interesuje nas znalezienie zliczeń wszystkich możliwych sum . ( jest dozwolone). $S_{ij} = a_i + a_j$ $i = j$

Jednym z algorytmów jest skonstruowanie wielomianu stopnia , i obliczenie jego kwadratu za pomocą metody transformacji Fouriera i odczytanie mocy z ich współczynniki w wynikowym wielomianu. Jest to algorytm czasu . $P(x) = \sum_{j=1}^{n} x^{a_j}$ $\le kn$ $O(n \log n)$

Mam dwa pytania:

Czy istnieje algorytm , który nie korzysta z FFT? $O(n \log n)$
Czy znane są lepsze algorytmy (tj. )? (FFT dozwolone). $o(n \log n)$

algorithms time-complexity fourier-transform

— Aryabhata
źródło

Dlaczego tak ważne jest, aby nie używać FFT? Wygląda na to, że masz już dobre rozwiązanie swojego problemu. Skąd bierze się wymóg nieużywania FFT? Wydaje mi się, że jest to raczej nienaturalny wymóg.

— DW

@DW: Ponieważ wtedy nie będzie pytania? :-) Jestem ciekawy, czy istnieje inne podejście.

— Aryabhata

Ok, rozumiem! Przyznaję, że też jestem ciekawy. :-) Dziękuję za interesujące pytanie.

— DW

@DW: Nie ma za co :-)

— Aryabhata

Wydaje się, że ten problem jest równoważny kwadratowi całkowitemu / wielomianowemu:

1. Wiadomo, że mnożenie wielomianowe jest równoważne mnożeniu liczb całkowitych .

2. Oczywiście, zredukowałeś już problem do kwadratu wielomianowego / całkowitego; dlatego ten problem jest co najwyżej tak trudny jak wyprostowanie.

Teraz zredukuję kwadrat całkowity do tego problemu:

Załóżmy, że masz algorytm:

F (\vec{a}) \to P^{2} (x), where P (x) = \sum_{a_{i} \in \vec{a}} x^{a_{i}}

$F(\mathbf{\vec a})\rightarrow P^2(x),\\ \text{where } P(x)=\sum_{a_i \in \mathbf{\vec a}} x^{a_i}$

Ten algorytm jest zasadniczo algorytmem, o który prosisz w swoim pytaniu. Tak więc, jeśli mam magiczny algorytm, który może to zrobić, mogę wykonać funkcję która wyrówna liczbę całkowitą ( o tak, kocham mathjax: P ): ${\rm S{\small QUARE}}\left(y\right)$ $y$

\begin{aligned} Algorithm 1 Squaring \\ 1. : & procedure S Q U A R E (y) : \\ 2. : & \vec{a} \leftarrow () & ▹ \vec{a} starts as empty polynomial sequence \\ 3. : & i \leftarrow 0 \\ 4. : & w h i l e y \neq 0 d o & ▹ break y down into a polynomial of base 2 \\ 5. : & i f y & 1 t h e n & ▹ if lsb of y is set \\ 6. : & \vec{a} \leftarrow \vec{a} i & ▹ append i to \vec{a} (appending x^{i}) \\ 7. : & e n d i f \\ 8. : & i \leftarrow i + 1 \\ 9. : & y \leftarrow y ≫ 1 & ▹ shift y right by one \\ 10. : & e n d w h i l e \\ 11. : & P^{2} (x) \leftarrow F (\vec{a}) & ▹ obtain the squared polynomial via F (\vec{a}) \\ 12. : & r e t u r n P^{2} (2) & ▹ simply sum up the polynomial \\ 13. : & end procedure \end{aligned}

$\begin{array}{rlr}\hline &\mathbf{\text{Algorithm 1}} \text{ Squaring}&\hspace{2em}&\\ \hline {\tiny 1.:}&\mathbf {\text{procedure }} {\rm S{\small QUARE}}\left(y\right):\\ {\tiny 2.:}&\hspace{2em}\mathbf {\vec a} \leftarrow () &&\triangleright~\mathbf {\vec a}\text{ starts as empty polynomial sequence}\\ {\tiny 3.:}&\hspace{2em}i \leftarrow 0\\ {\tiny 4.:}&\hspace{2em}\mathbf{while}~y\ne0~\mathbf{do} &&\triangleright~\text{break }y\text{ down into a polynomial of base }2\\ {\tiny 5.:}&\hspace{4em}\mathbf{if}~y~\&~1~\mathbf{then} &&\triangleright~\text{if lsb of }y\text{ is set}\\ {\tiny 6.:}&\hspace{6em}\mathbf{\vec a} \leftarrow \mathbf{\vec a}i &&\triangleright~\text{append }i\text{ to }\mathbf{\vec a}~\text{(appending }x^i\text{)}\\ {\tiny 7.:}&\hspace{4em}\mathbf{end~if}\\ {\tiny 8.:}&\hspace{4em}i \leftarrow i + 1\\ {\tiny 9.:}&\hspace{4em}y \leftarrow y \gg 1 &&\triangleright~\text{shift }y\text{ right by one}\\ {\tiny 10.:}&\hspace{2em}\mathbf{end~while}\\ {\tiny 11.:}&\hspace{2em}P^2(x) \leftarrow F\left(\mathbf{\vec a}\right) &&\triangleright~\text{obtain the squared polynomial via } F\left(\mathbf{\vec a}\right)\\ {\tiny 12.:}&\hspace{2em}\mathbf{return}~P^2(2) &&\triangleright~\text{simply sum up the polynomial}\\ {\tiny 13.:}&\mathbf {\text{end procedure}}\\ \hline &\end{array}$

Python ( test przy pomocy codepad ):

#/cs//q/11418/2755

def F(a):
    n = len(a)
    for i in range(n):
        assert a[i] >= 0

    # (r) => coefficient
    # coefficient \cdot x^{r}
    S = {}
    for ai in a:
        for aj in a:
            r = ai + aj

            if r not in S:
                S[r] = 0

            S[r] += 1

    return list(S.items())

def SQUARE(x):
    x = int(x)

    a = []
    i = 0
    while x != 0:
        if x & 1 == 1:
            a += [i]
        x >>= 1
        i += 1

    print 'a:',a
    P2 = F(a)

    print 'P^2:',P2

    s = 0
    for e,c in P2:
        s += (1 << e)*c
    return s

3. Zatem kwadratowanie jest co najwyżej tak trudne, jak ten problem.

4. Dlatego kwadratowanie liczb całkowitych jest równoważne temu problemowi. (każda z nich jest co najwyżej tak trudna ze względu na ( 2 , 3 , 1 ))

$\mathcal O(n\log n)$ $\mathcal O(n \log n \log \log n)$ $\mathcal O\left(n \log n\,2^{\mathcal O(\log^* n)}\right)$ $\Omega\left(n \log n\right)$

$\mathcal O\left(n\log n\right)$

5. Teraz twój problem nie polega na mnożeniu, lecz na kwadracie. Czy kwadratura jest łatwiejsza? Cóż, jest to otwarty problem (na razie nie) : nie wiadomo, że w kwadracie występuje szybszy algorytm niż mnożenie. Jeśli możesz znaleźć lepszy algorytm dla swojego problemu niż użycie mnożenia; to prawdopodobnie byłby przełom.

$\mathcal O(n\log n)$ $\mathcal O(n\log n)$ $\mathcal O(n \log n)$ $\mathcal O(n\log n)$ albo, ponieważ najlepszy algorytm mnożenia zbliża się tylko do tej złożoności.

— Realz Slaw
źródło