Алгоритм БПФ для попарных сумм

14

Предположим, что нам дано различных целых чисел , таких что для некоторой константы и для всех .a 1 , a 2 , , a n 0 a ik n k > 0 ina1,a2,,an0aiknk>0я

Нас интересует нахождение отсчетов всех возможных попарных сумм Sij=ai+aj . ( i=j разрешено).

Один алгоритм состоит в том, чтобы построить многочлен P(x)=j=1nxaj степени kn , вычислить его квадрат, используя метод преобразования Фурье, и считать значения с помощью их коэффициенты в полученном полиноме. Это алгоритм O(nlogn) времени.

У меня есть два вопроса:

  • Есть ли алгоритм O(nlogn) , который не использует БПФ?

  • Известны ли лучшие алгоритмы (например, o(nlogn) )? (БПФ разрешен).

Арьябхата
источник
Почему важно не использовать БПФ? Похоже, у вас уже есть хорошее решение вашей проблемы. Откуда возникает требование не использовать БПФ? Это звучит для меня как довольно неестественное требование навязывать.
DW
@DW: Потому что тогда не будет вопроса, чтобы спросить? :-) Мне просто любопытно узнать, есть ли другой подход.
Арьябхата
Хорошо понял! Признаюсь, мне тоже любопытно. :-) Спасибо за интересный вопрос.
DW
@DW: Добро пожаловать :-)
Aryabhata

Ответы:

8

Казалось бы, эта проблема эквивалентна целочисленному / полиномиальному квадрату:

1. Известно, что полиномиальное умножение эквивалентно целочисленному умножению .

2. Очевидно, вы уже свели задачу к полиномиальному / целочисленному квадрату; поэтому эта проблема не более, чем квадрат.

Теперь я приведу целочисленный квадрат к этой задаче:

Предположим, у вас был алгоритм:

F(a)п2(Икс),где п(Икс)знак равноΣaяaИксaя

Этот алгоритм по сути является алгоритмом, который вы запрашиваете в своем вопросе. Таким образом, если бы у меня был магический алгоритм, который может это сделать, я мог бы создать функцию которая возведет в квадрат целое число y ( о да, я люблю mathjax: P ):SQUAрЕ(Y)Y

Algorithm 1 Squaring1.:procedure SQUARE(y):2.:a() a starts as empty polynomial sequence3.:i04.:while y0 do break y down into a polynomial of base 25.:if y & 1 then if lsb of y is set6.:aai append i to a (appending xi)7.:end if8.:ii+19.:yy1 shift y right by one10.:end while11.:P2(x)F(a) obtain the squared polynomial via F(a)12.:return P2(2) simply sum up the polynomial13.:end procedure

Python ( тест с кодовой панелью ):

#/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. Таким образом, возведение в квадрат не более, чем эта проблема.

4. Следовательно, целочисленное возведение в квадрат эквивалентно этой задаче. (каждый из них не более, чем друг с другом, из-за ( 2 , 3 , 1 ))

O(nlogn)O(nlognloglogn)O(nlogn2O(logn))Ω(nlogn)

O(nlogn)

5. Теперь ваша проблема не в умножении, а в квадрате. Так проще ли возводить в квадрат? Что ж, это открытая проблема (на данный момент нет) : неизвестно, что в квадрате используется более быстрый алгоритм, чем умножение. Если бы вы могли найти лучший алгоритм для вашей задачи, чем использование умножения; тогда это, вероятно, будет прорывом.

O(nlogn)O(nlogn)O(nlogn)O(nlogn) либо, поскольку лучший алгоритм умножения только приближается к этой сложности.

Реал Слав
источник