Weźmy dwa wielomiany stopnia n, wtedy pomnożenie ich zajmie czas \(\displaystyle{ n^2}\). Istnieją jednak podobno algorytmy robiące to w czasie \(\displaystyle{ n \cdot \ln \left( n \right)}\)
I tego nie rozumiem - wielomian ma n+1 współczynników, każdy z nich zależy od współczynników drugiego wielomianu. Jak uzyskać mniejszy czas niż kwadratowy?
[Algorytmy] Szybkie mnożenie wielomianów
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
[Algorytmy] Szybkie mnożenie wielomianów
wynik mnożenia to \(\displaystyle{ O(n)}\) liczb, zatem potencjalnie nie ma żadnych przeszkód w obliczaniu ich szybciej niż \(\displaystyle{ O(n^2)}\)