Zaawansowane algorytmy i struktury danych/Wykład 4

Abstrakt

Naturalna metoda dodawania dwóch wielomanów wymaga czasu $\mathrm{\Theta }(n)$, natomiast prosty algorytm mnożenia dwóch wielomianów stopnia $n$ wymaga czasu $\mathrm{\Theta }(n^2)$. W wykładzie tym pokażemy, jak z wykożytaniem szybkiej transformaty Fouriera (STF), wykonać wszystkie podstawowe opreracje na wielomianach w czasie większym niż $\mathrm{\Theta }(n)$ o czynnik polilogarytmiczny. Pokażemy jak dla wielomianów stopnia $n$:

• mnożyć je w czasie $O(n\log n)$,
• obliczać wielomian interpolacyjny w czasie $O(n{\log }^{2}n)$,
• obliczać wartość wielomianiu w $n$ punktach w czasie $O(n{\log }^{2}n)$,
• dzielić wielomiany w czasie $O(n{\log }^{3}n)$.