[Algorytmy] Szybkie mnożenie wielomianów

Awatar użytkownika
Borneq
Użytkownik
Użytkownik
Posty: 247
Rejestracja: 23 lip 2010, o 07:50
Płeć: Mężczyzna
Lokalizacja: geo:lat=0 geo:lon=0
Podziękował: 13 razy

[Algorytmy] Szybkie mnożenie wielomianów

Post autor: Borneq »

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?
Ostatnio zmieniony 8 lip 2014, o 11:47 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Adifek
Użytkownik
Użytkownik
Posty: 1567
Rejestracja: 15 gru 2008, o 16:38
Płeć: Mężczyzna
Lokalizacja: Ostrzeszów/Wrocław
Podziękował: 8 razy
Pomógł: 398 razy

[Algorytmy] Szybkie mnożenie wielomianów

Post autor: Adifek »

Google boli? Drugi wynik:
... ka/fft.pdf
Awatar użytkownika
Zordon
Użytkownik
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

Post autor: Zordon »

wynik mnożenia to \(\displaystyle{ O(n)}\) liczb, zatem potencjalnie nie ma żadnych przeszkód w obliczaniu ich szybciej niż \(\displaystyle{ O(n^2)}\)
ODPOWIEDZ