Вопросы с тегом «fft»

16
Нахождение свидетеля у Минковского суммы целых чисел

Пусть AA и BB - подмножества {0,…,n}\{0,\ldots,n\} . Нам интересно найти сумму Минковского A+B={a+b | a∈A,b∈B}A+B=\{a+b~|~a\in A,b\in B\} . χX:{0,…,2n}→{0,1}\chi_X:\{0,\ldots,2n\}\to \{0,1\} является характеристической функциейXX еслиχX(x)={1 if x∈X0 otherwise\chi_X(x) = \begin{cases} 1 \text{ if }...

10
Сложность свертки в кольце max / plus

Мы можем сделать свертку в для полиномов плюс / умножение с FFT. Тем не менее, подход не кажется очень обобщенным для колец в целом. Был ли какой-нибудь прогресс по наивной свертке для кольца max / plus?O ( n logн )О(Nжурнал⁡N)O(n\log n)O ( n2)О(N2)O(n^2) Я должен отметить, что можно преобразовать...