Предположим, что нам дано различных целых чисел , таких что для некоторой константы и для всех .a 1 , a 2 , … , a n 0 ≤ a i ≤ k n k > 0 i
Нас интересует нахождение отсчетов всех возможных попарных сумм . ( разрешено).
Один алгоритм состоит в том, чтобы построить многочлен степени , вычислить его квадрат, используя метод преобразования Фурье, и считать значения с помощью их коэффициенты в полученном полиноме. Это алгоритм времени.
У меня есть два вопроса:
Есть ли алгоритм , который не использует БПФ?
Известны ли лучшие алгоритмы (например, )? (БПФ разрешен).
algorithms
time-complexity
fourier-transform
Арьябхата
источник
источник
Ответы:
Казалось бы, эта проблема эквивалентна целочисленному / полиномиальному квадрату:
1. Известно, что полиномиальное умножение эквивалентно целочисленному умножению .
2. Очевидно, вы уже свели задачу к полиномиальному / целочисленному квадрату; поэтому эта проблема не более, чем квадрат.
Теперь я приведу целочисленный квадрат к этой задаче:
Предположим, у вас был алгоритм:
Этот алгоритм по сути является алгоритмом, который вы запрашиваете в своем вопросе. Таким образом, если бы у меня был магический алгоритм, который может это сделать, я мог бы создать функцию которая возведет в квадрат целое число y ( о да, я люблю mathjax: P ):S Q U A R E ( у) Y
Python ( тест с кодовой панелью ):
3. Таким образом, возведение в квадрат не более, чем эта проблема.
4. Следовательно, целочисленное возведение в квадрат эквивалентно этой задаче. (каждый из них не более, чем друг с другом, из-за ( 2 , 3 , 1 ))
5. Теперь ваша проблема не в умножении, а в квадрате. Так проще ли возводить в квадрат? Что ж, это открытая проблема (на данный момент нет) : неизвестно, что в квадрате используется более быстрый алгоритм, чем умножение. Если бы вы могли найти лучший алгоритм для вашей задачи, чем использование умножения; тогда это, вероятно, будет прорывом.
источник