89
правок
Изменения
Нет описания правки
Q(t) = Q(t) * Q(-t);
leave a[i] with (i % 2 == n % 2);
Q: t^2 2i -> t^i;
n = n div 2;
}
return a[n];
</code>
Вычисление <tex>a[k], a[k + 1], \cdots , a[2k - 1]</tex> занимает <tex>O(k^2)</tex> времени, ибо их всего <tex>k</tex>, а каждое считается за <tex>O(k)</tex>. Умножение многочленов длины порядка <tex>k</tex> также занимает <tex>O(k^2)</tex> времени. Итераций внешнего цикла будет <tex>O(logn)</tex> в силу того, что мы делим <tex>n</tex> на <tex>2</tex> каждый раз. Итого мы получили алгоритм, работающий за <tex>O(k^2 \cdot logn)</tex>
