Możemy wykonać splot w dla wielomianów dodatnich / wielokrotnych za pomocą FFT. Jednak podejście to nie wydaje się zbyt ogólne w odniesieniu do pierścieni w ogóle. Czy nastąpił postęp w stosunku do naiwnego splotu dla pierścienia max / plus?
algebra
polynomials
fft
convolution
Thomas Ahle
źródło
źródło
Odpowiedzi:
Istnieje bardziej ogólne pytanie dotyczące przepływu matematyki .
Zadałem podobne pytanie na CS.SE . jbapple podał dobrą odpowiedź. Cytować
Wszelkie ulepszenia tego ograniczenia rzucą światło na kilka trudnych otwartych problemów, takich jak sortowanie i wszystkie najkrótsze ścieżki.X+Y
Jeśli jedna z funkcji jest wypukła / wklęsła, możemy rozwiązać problem w czasie . Patrz „Przyspieszenie programowania dynamicznego”, Eppstein i in. .O(nlogn)
źródło