Archive

Posts Tagged ‘перетворення Фур’є’

Многочлени і перетворення Фур’є

Прямолінійний метод додавання двох многочленів вимагає \Theta(n) часу, а для множення — \Theta(n^2). Оскільки множення многочленів має значну практичну важливість, у цій статті ми покажемо як швидке перетворення Фур’є допомагає скоротити час на множення двох многочленів до \Theta(n \lg{n}).
Читати далі…