Algoritmo

Supongamos que se nos dan enteros distintos , de modo que para alguna constante , y para todo .$n$$a_1, a_2, \dots, a_n$$0 \le a_i \le kn$$k \gt 0$$i$

Estamos interesados ​​en encontrar los recuentos de todas las sumas por parejas posibles . ( está permitido).$S_{ij} = a_i + a_j$$i = j$

Un algoritmo es construir el polinomio de grado , y calcular su cuadrado utilizando el método de transformación de Fourier y leer las potencias con sus coeficientes en el polinomio resultante. Este es un algoritmo de tiempo .$P(x) = \sum_{j=1}^{n} x^{a_j}$$\le kn$$O(n \log n)$

Tengo dos preguntas:

• ¿Existe un algoritmo que no use FFT?$O(n \log n)$

• ¿Se conocen mejores algoritmos (es decir, )? (FFT permitido).$o(n \log n)$

Parece que este problema es equivalente a la cuadratura entera / polinómica:

1. Se sabe que la multiplicación polinómica es equivalente a la multiplicación entera .

2. Obviamente, ya redujo el problema a cuadratura polinómica / entera; por lo tanto, este problema es tan difícil como cuadrar.

Ahora reduciré la cuadratura entera a este problema:

Supongamos que tienes un algoritmo:

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

Este algoritmo es esencialmente el algoritmo que solicita en su pregunta. Por lo tanto, si tuviera un algoritmo mágico que pueda hacer esto, puedo hacer una función, que cuadrará el número entero y ( oh sí, amo mathjax: P ):${\rm S{\small QUARE}}\left(y\right)$$y$

$$\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 ( prueba con teclado ):

#/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. Por lo tanto, la cuadratura es tan difícil como este problema.

4. Por lo tanto, la cuadratura entera es equivalente a este problema. (cada uno es tan duro como el otro, debido a ( 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. Ahora, su problema no es exactamente la multiplicación, es la cuadratura. Entonces, ¿es más fácil la cuadratura? Bueno, es un problema abierto (no por ahora) : no se sabe que la cuadratura tenga un algoritmo más rápido que la multiplicación. Si pudiera encontrar un mejor algoritmo para su problema que usar la multiplicación; entonces esto probablemente sería un gran avance.

$\mathcal O(n\log n)$$\mathcal O(n\log n)$$\mathcal O(n \log n)$$\mathcal O(n\log n)$ tampoco, ya que el mejor algoritmo de multiplicación solo se acerca a esa complejidad.